Strings Notes.docx

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING BAPATLA ENGINEERING COLLEGE::BAPATLA AUTONOMOUS CLASS:II/IV B.Tech A,B&C

Max.Marks:10

SUB:atfl/14CS502

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

DATE:23/9/2016

State pumping lemma for regular languages List out closure properties of regular languages What is CFL What is CFG What is Left most derivation What is right most derivation What is derivation What is parse tree What is nullable variable What is unit production What is epsilon production What is useless symbol What is reduced grammar What is CNF What is GNF What is the language of CFG What is sentential form What is the use of pumping lemma 1. a). Construct CFG for L={0a 1b 2c / b=a+c} b). Give left most, right most derivations and parse tree for the string ‘aabbabba’ to the grammar SaB | bA Aa | aS | bAA Bb | bS | aBB 2. a). Construct CFG for L={ai bj ck / i=j or j=k} b). Show that the following grammar is ambiguous. EE+E | E*E | E |id 3. Convert the following into CNF. SAACD AaAb | ε CaC | a DaDa | bDb | ε 4. Convert the following into GNF G=({A1,A2,A3 }, {a,b}, P, A1) P: A1 A2A3 A2 A3A1 | b A3 A1A2 | a 5. a). Give the proof of pumping lemma for regular languages. b). Prove that L={0p/ p is prime} is not regular. 6. a). Minimize the following DFA.

A B C *D E F G H

0 B A D D D G F G

b). Construct grammar for the language L={ambn |m≥n}

1 A C B A F E G D

Duration:50mins