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 note Theory of automata - Lecture 29 Lecture 5 Theory Of Automata By Dr. MM Alam 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 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 tripled or b is tripled but not both. This means each word contains the substring aaa or the substring bbb but not both. Λ b bb a ab abb aaa Λ b bb a ab abb Λ a aa b ba baa bbb Λ a aa b ba baa Let r1 r2 and r3 be three regular expressions. Show that the language associated with r1 r2 r3 is the same as the language associated with r1r3 r2r3. Show that r1 r2 r3 is equivalent to r1r2 r1r3. This will be the same as providing a distributive law for regular expressions. r1 r2 r3 The first expression can be either r1 or r2. The second expression is always r3. There are two possibilities for this language r1r3 or r2r3. r1 r2 r3 The first expression is always r1. It is followed by either r2 or r3. Question Can a language be expressed by more than one regular expressions while given that a unique language is generated by that regular expression Deterministic Finite Automata Also known as Finite state machine Finite state automata It represents an abstract machine which is used to represent a regular language A regular expression can also be .

• 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