1. Lecture # 25 Theory Of Automata By Dr. MM Alam 1
2. Lecture#24 at a glance… • Unrestricted Grammars Example • User controlled Parsing in JFLAP • Regular Grammar Conversion to FA
3. 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
4. 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
5. 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
6. 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
7. Regular Grammar • The corresponding TG: S → aA | bB A → aS | a B → bS | b 7
8. • Regular Grammar Conversion to FA using JFLAP • Practical Demonstration
9. 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
10. 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 10
11. 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
12. 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 old CFG: (Next slide) 12
13. Regular Grammar • OLD CFG: Derivation Production Used S => aSa S → aSa => aaSaa S → aSa => S → bSb aabSbaa => aabbaa S →ʎ 13
14. Regular Grammar • New CFG • We can combine the last two steps . Derivation Production Used Derivation Production Used S => aSa S → aSa S => S → => aaSaa S → aSa aSa aSa => S → => S → bSb aaSaa aSa aabSbaa => S → bb => aabbaa S →ʎ aabbaa 14
15. Null Production Elimination EXAMPLE • Consider the CFG for the language defined by (a + b)*a S → Xa X → aX I bX I ʎ • The only nullable nonterminal here is X, 15
16. Null Production Elimination • The productions that have right sides including X are: Productions with Nullables S → Xa X → aX X → bX New Productions Formed by the Rule S→ a X→a 16
17. Null Production Elimination • The full new CFG is: S → Xa I a X → aX | bX | a I b Derivation Production Used • To produce the word baa we S => Xa S → Xa formerly used the derivation shown=> bXa X → bX In the table. => baXa X → aX => baa X →ʎ 17
18. Null Production Elimination • Combine the last two steps, and the new derivation in the new CFG is: Derivation Production Derivation Production Used Used S => Xa S → Xa S => Xa S → Xa => bXa X → bX => bXa X → bX => baXa X → aX => baa X →a => baa X →ʎ 18
19. Null Production Elimination • Consider this CFG for the language defined by (a + b)*bb(a + b)* S → XY X → Zb Y → bW Z → AB W→Z A → aA I bA I ʎ 19
20. Null Production Elimination • The modified replacement algorithm tells us to generate new productions to replace the ʎ -productions as follows: Old New Productions X → Zb X→b Y → bW Y→b Z → AB Z → A and Z → B W→Z Nothing new A → aA A→a A → bA A→b B → Ba B→a 20