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 note Theory of automata - Lecture 16 Lecture 25 Theory Of Automata By Dr. MM Alam 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 S aaS l bbS I abXI baX I λ Np wq X aaX l bbX l abS l baS TG is 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 gt aSa gt aaSaa gt aabSbaa 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 longer be derived. For example the derivation is generated in the .