flat qp
1. State the nullable variables from the following CFG. SABCa | bD ABC |b Bb | ε CĐ | ε Dd 2. Write the difference between Pushdown Automata and Turing Machine. 3. Construct a Turing Machine to accept strings formed with 0 and 1 and having substring 000. 4. Write a short notes on NP complete , NP hard problems 1. Discuss the Pumping lemma for Context Free Languages concept with example {anbncn where n>0}? 2. Construct a Turing Machine to accept the following language. L = { 0n1n0n | n ≥1} 3. Write a note on Modified PCP and Multi tape Turing machine. 4. Write a short notes on Chomsky hierarchy. 1. Use the following grammar : S à ABC | BbB A à aA | BaC|aaa B à bBb| a|D C à CA|AC D à ⏀ Eliminate ε -productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Convert the resulting grammar into Chomsky Norma