ZeePedia

Table of Contents

What does automata mean, Introduction to languages >>
img
Theory of Automata
(CS402)
Table of contents:
Lecture N0. 1 .......................................................................................................................................................... 4
Summary............................................................................................................................................................ 4
What does automata mean? ............................................................................................................................... 4
Introduction to languages................................................................................................................................... 4
Alphabets ........................................................................................................................................................... 4
Strings ................................................................................................................................................................ 4
Defining Languages........................................................................................................................................... 5
Lecture N0. 2 .......................................................................................................................................................... 9
Summary............................................................................................................................................................ 9
Kleene Star Closure ........................................................................................................................................... 9
Recursive definition of languages...................................................................................................................... 9
Lecture N0. 3 ........................................................................................................................................................ 11
Summary.......................................................................................................................................................... 11
Regular Expression .......................................................................................................................................... 11
Recursive definition of Regular Expression(RE)............................................................................................. 11
Method 3 (Regular Expressions) ..................................................................................................................... 11
Lecture N0. 4 ........................................................................................................................................................ 12
Equivalent Regular Expressions ...................................................................................................................... 12
Method 4 (Finite Automaton) .......................................................................................................................... 13
Lecture N0. 5 ........................................................................................................................................................ 15
Lecture N0. 6 ........................................................................................................................................................ 17
Equivalent FAs ................................................................................................................................................ 17
Lecture N0. 7 ........................................................................................................................................................ 20
FA corresponding to finite languages .............................................................................................................. 20
Method 5 (Transition Graph) ........................................................................................................................... 22
Lecture N0. 8 ........................................................................................................................................................ 23
Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa,
containing aa or bb........................................................................................................................................... 23
Lecture N0. 9 ........................................................................................................................................................ 25
Generalized Transition Graphs ........................................................................................................................ 27
Lecture N0. 10 ...................................................................................................................................................... 28
Nondeterminism............................................................................................................................................... 29
Kleene's Theorem............................................................................................................................................ 29
Lecture N0. 11 ...................................................................................................................................................... 30
Proof(Kleene's Theorem Part II) ..................................................................................................................... 30
Lecture N0. 12 ...................................................................................................................................................... 34
Kleene's Theorem Part III ............................................................................................................................... 35
Lecture N0. 13 ...................................................................................................................................................... 38
Lecture N0. 14 ...................................................................................................................................................... 41
Lecture N0. 15 ...................................................................................................................................................... 44
Nondeterministic Finite Automaton (NFA) .................................................................................................... 44
Converting an FA to an equivalent NFA ......................................................................................................... 45
Lecture N0. 16 ...................................................................................................................................................... 47
NFA with Null String ...................................................................................................................................... 47
Lecture N0. 17 ...................................................................................................................................................... 50
NFA and Kleene's Theorem ............................................................................................................................ 50
Lecture N0. 18 ...................................................................................................................................................... 53
NFA corresponding to Concatenation of FAs.................................................................................................. 53
NFA corresponding to the Closure of an FA ................................................................................................... 55
Lecture N0. 19 ...................................................................................................................................................... 57
Memory required to recognize a language....................................................................................................... 57
Distinguishable strings and Indistinguishable strings ...................................................................................... 58
Lecture N0. 20 ...................................................................................................................................................... 60
Finite Automaton with output .......................................................................................................................... 60
Moore machine ................................................................................................................................................ 60
Lecture N0. 21 ...................................................................................................................................................... 62
Mealy machine................................................................................................................................................. 62
Lecture N0. 22 ...................................................................................................................................................... 65
2
img
Theory of Automata
(CS402)
Equivalent machines ........................................................................................................................................ 65
Lecture N0. 23 ...................................................................................................................................................... 68
Lecture N0. 24 ...................................................................................................................................................... 70
Regular languages............................................................................................................................................ 70
Complement of a language .............................................................................................................................. 71
Lecture N0. 25 ...................................................................................................................................................... 73
Nonregular languages ...................................................................................................................................... 76
Lecture N0. 26 ...................................................................................................................................................... 77
Pumping Lemma.............................................................................................................................................. 77
Lecture N0. 27 ...................................................................................................................................................... 80
Pumping Lemma version II ............................................................................................................................. 80
Lecture N0. 28 ...................................................................................................................................................... 82
Pseudo theorem................................................................................................................................................ 83
Lecture N0. 29 ...................................................................................................................................................... 84
Decidability...................................................................................................................................................... 84
Determining whether the two languages are equivalent or not ? ..................................................................... 85
Lecture N0. 30 ...................................................................................................................................................... 88
Lecture N0. 31 ...................................................................................................................................................... 92
Context Free Grammar (CFG) ......................................................................................................................... 92
CFG terminologies........................................................................................................................................... 92
Lecture N0. 32 ...................................................................................................................................................... 95
Trees ................................................................................................................................................................ 96
Lecture N0. 33 ...................................................................................................................................................... 98
Polish Notation (o-o-o) .................................................................................................................................... 99
Lecture N0. 34 .................................................................................................................................................... 101
Total language tree......................................................................................................................................... 101
Regular Grammar .......................................................................................................................................... 102
Lecture N0. 35 .................................................................................................................................................... 104
Null Production.............................................................................................................................................. 104
Lecture N0. 36 .................................................................................................................................................... 107
Chomsky Normal Form (CNF) ...................................................................................................................... 107
Lecture N0. 37 .................................................................................................................................................... 110
A new format for FAs .................................................................................................................................... 110
Lecture N0. 38 .................................................................................................................................................... 114
Nondeterministic PDA................................................................................................................................... 116
Lecture N0. 39 .................................................................................................................................................... 119
PDA corresponding to CFG........................................................................................................................... 119
Lecture N0. 40 .................................................................................................................................................... 123
Conversion form of PDA ............................................................................................................................... 124
Lecture N0. 41 .................................................................................................................................................... 126
Lecture N0. 42 .................................................................................................................................................... 129
Lecture N0. 43 .................................................................................................................................................... 132
Non-Context-Free language........................................................................................................................... 132
Pumping lemma for CFLs.............................................................................................................................. 133
Lecture N0. 44 .................................................................................................................................................... 139
Decidablity..................................................................................................................................................... 139
Parsing Techniques ........................................................................................................................................ 142
Lecture N0. 45 .................................................................................................................................................... 147
Turing machine .............................................................................................................................................. 147
3
Table of Contents:
  1. What does automata mean, Introduction to languages
  2. Kleene Star Closure, Recursive definition of languages
  3. Regular Expression, Recursive definition of Regular Expression
  4. Equivalent Regular Expressions
  5. Finite Automaton
  6. Equivalent FAs
  7. FA corresponding to finite languages
  8. Examples of TGs: accepting all strings
  9. Generalized Transition Graphs
  10. Nondeterminism, Kleene’s Theorem
  11. Proof(Kleene’s Theorem Part II)
  12. Kleene’s Theorem Part III
  13. Concatenation of FAs
  14. Closure of an FA
  15. Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
  16. NFA with Null String
  17. NFA and Kleene’s Theorem
  18. NFA corresponding to Concatenation of FAs
  19. Distinguishable strings and Indistinguishable strings
  20. Finite Automaton with output, Moore machine
  21. Mealy machine
  22. Equivalent machines
  23. Mealy machines in terms of sequential circuit
  24. Regular languages, Complement of a language
  25. Nonregular languages
  26. Pumping Lemma
  27. Pumping Lemma version II
  28. Pseudo theorem
  29. Decidability
  30. finiteness of a language
  31. Context Free Grammar (CFG), CFG terminologies
  32. Trees
  33. Polish Notation (o-o-o)
  34. Total language tree, Regular Grammar
  35. Null Production
  36. Chomsky Normal Form (CNF)
  37. A new format for FAs
  38. Nondeterministic PDA
  39. PDA corresponding to CFG
  40. Conversion form of PDA
  41. Conversion Form, Joints of the machine
  42. Row language, Nonterminals
  43. Non-Context-Free language, Pumping lemma for CFLs
  44. Decidablity, Parsing Techniques
  45. Turing machine