tailieunhanh - Lecture note Theory of automata - Lecture 16

This chapter presents the following content: Examples of Kleene’s theorem part III (method 3), NFA, examples, avoiding loop using NFA, example, converting FA to NFA, examples, applying an NFA on an example of maze, NFA with null string, examples, RE corresponding to NFA with null string (task), converting NFA to FA (method 1,2,3) examples, NFA and Kleene’s theorem method 1, examples, NFA and Kleene’s theorem method 2, examples. | Lecture # 25 Theory Of Automata By Dr. MM Alam 1 1 Lecture#24 at a glance Unrestricted Grammars Example User controlled Parsing in JFLAP Regular Grammar Conversion to FA FA Conversion to Regular grammar EXAMPLE 3 Consider the CFG: S → aaS l bbS I abXI baX I λ X → aaX l bbX l abS l baS The algorithm tells us that there will be three states: -, X, +. 3 FA Conversion to Regular grammar EXAMPLE 3 Since there is only one production of the form Np → wq TG is 4 S → aaS l bbS I abXI baX I λ X → aaX l bbX l abS l baS Book page 264 4 FA Conversion to Regular grammar EXAMPLE 4 Consider the CFG: S → aA | bB A → aS | a B → bS | b This language can be defined by the regular expression (aa + bb)+. It does not have any productions of the form Nx →ʎ 5 Important Point For a CFG to accept the word ʎ, it must have at least one production of this form, called a ʎ -production. A ʎ -production need not imply that ʎ is in the language, as with S → aX X → ʎ 6 Regular Grammar The corresponding TG: S → aA | bB | Lecture # 25 Theory Of Automata By Dr. MM Alam 1 1 Lecture#24 at a glance Unrestricted Grammars Example User controlled Parsing in JFLAP Regular Grammar Conversion to FA FA Conversion to Regular grammar EXAMPLE 3 Consider the CFG: S → aaS l bbS I abXI baX I λ X → aaX l bbX l abS l baS The algorithm tells us that there will be three states: -, X, +. 3 FA Conversion to Regular grammar EXAMPLE 3 Since there is only one production of the form Np → wq TG is 4 S → aaS l bbS I abXI baX I λ X → aaX l bbX l abS l baS Book page 264 4 FA Conversion to Regular grammar EXAMPLE 4 Consider the CFG: S → aA | bB A → aS | a B → bS | b This language can be defined by the regular expression (aa + bb)+. It does not have any productions of the form Nx →ʎ 5 Important Point For a CFG to accept the word ʎ, it must have at least one production of this form, called a ʎ -production. A ʎ -production need not imply that ʎ is in the language, as with S → aX X → ʎ 6 Regular Grammar The corresponding TG: S → aA | bB A → aS | a B → bS | b 7 Regular Grammar Conversion to FA using JFLAP Practical Demonstration Elimination of null production Theorem Statement: If L is a context-free language generated by a CFG that includes ʎ -productions then there is a different context-free grammar that has no ʎ -productions that generates either the whole language L (if L does not include the word ʎ) or else generates the language of all the words in L that are not ʎ. 9 Proof (by Example) Consider CFG for EVENPALINDROME (the palindromes with an even number of letters): S → aSa I bSb I ʎ Following possible derivation: S => aSa => aaSaa => aabSbaa => aabbaa 10 Proof (Cont’d ) When we apply this replacement rule to the following CFG. S → aSa I bSb I ʎ We remove the production S → ʎ and replace it with S → aa and S → bb, These are the first two productions with the right-side S deleted. 11 Proof (Cont’d ) The CFG is now: S → aSa I bSb I aa I bb Which also generates EVENPALINDROME, except for the word ʎ, which can no