TAILIEUCHUNG - Lecture note Theory of automata - Lecture 29

This chapter includes contents: Example of prefixes of a language, Theorem: pref(Q in R) is regular, proof, example, Decidablity, deciding whether two languages are regular or not?, method 1, example, method 2, example. | Lecture # 5 Theory Of Automata By Dr. MM Alam 1 Lecture#4 Recap Recursive way of defining languages Recursive way examples Regular expressions Regular expression examples Construct a regular expression for all words that contain exactly two b’s or exactly three b’s, not more. a*ba*ba* + a*ba*ba*ba* or a*(b + Λ)a*ba*ba* Construct a regular expression for: (i) all strings that end in a double letter. (ii) all strings that do not end in a double letter (i) (a + b)*(aa + bb) (ii) (a + b)*(ab + ba) + a + b + Λ Construct a regular expression for all strings that have exactly one double letter in them (b + Λ)(ab)*aa(ba)*(b + Λ) + (a + Λ)(ba)*bb(ab)*(a + Λ) Construct a regular expression for all strings in which the letter b is never tripled. This means that no word contains the substring bbb (Λ + b + bb)(a + ab + abb)* Words can be empty and start and end with a or b. A compulsory ‘a’ is inserted between all repetitions of b’s. Construct a regular expression for all words in which a is .

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Prefixes of a language
• Decidable problem
• 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
• Computer science
• 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