TAILIEUCHUNG - Lecture note Theory of automata - Lecture 30

Lecture Theory of automata - Lecture 30 includes contents: Deciding whether two languages are equivalent or not, example, deciding whether an FA accept any string or not, method 3, examples, finiteness of a language. | Lecture # 6 Theory Of Automata By Dr. MM Alam 1 Lecture#5 Recap Introduction to Finite Automata Finite Automata representation using Transition tables and using graphs Finite Automata examples 1 a 0 b a,b Given an input string, an FA will either accept or reject the input based on the following: If final state is reached after reading the string, the FA will accept the string If the final state is not reachable after reading the individual symbols of a string, then FA will reject the string. Construct a regular expression and correspondingly an FA for all words in which a appears tripled, if at all. The regular expression is as follows:- (aaa+b)* 6 2 a a,b 1 - a b 3 5+ a b b 4+ a,b a, b Construct a regular expression and correspondingly an FA for all strings that end in a double letter. The regular expression is as follows:- (a+b)*(aa+bb) 3+ 1 a 1 - a b 2+ b a 4+ b a b a b L1 = The language of strings, defined over Σ={a, b}, beginning with b a,b b a a,b –– + 1 The language of .

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Decidable problem
• Computer science
• Automata theory
• Automata theory languages
• Automata theory computation
• Pushdown automata
• Context Free grammars
• Regular languages
• Additional classes
• Intractable problems
• Properties of context free languages
• Solution of the task
• Polish notation
• Total language tree
• Null production
• Nullable production
• Theorem regarding CNF
• The START state
• Nondeterministic PDA
• Equivalent PDA
• PDA corresponding to CFG
• STACK alphabet
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• Parsing techniques
• Turing machine
• DELETE subprogram
• Kleene’s theorem
• NFA corresponding
• Concatenation of FAs
• Distinguishable strings
• Indistinguishable strings
• Recap theorem
• Moore machine
• Mealy machine
• Applications of complementing
• Equivalent machines
• Mealy machines
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I