Push Down Automata &
Turing Machine (Unit-3)
Descriptive Questions
Q1. What are undecidable problems? Explain with example.
Q2. Define Recursively Enumerable Language.
Q3. Define NP hard and NP completeness problem.
Q4. Define CFG and what is the importance of it in compiler construction?
Q5. List the components of a Turing Machine. State Universal Turing Machine.
Q6. Construct Turing machine for the languages containing the set of all strings of balanced paranthesis?
Q7. Explain the different types of Turing Machine.
Q8. Give an overview of recursively enumerable language.
Q9. Given a CFG, construct an equivalent PDA.
Grammar: S → aSb | ε
Detail the steps and transitions in the PDA.
Q10. Explain about Halting Problem of Turing machine.
