Stack: One additional component available as part of PDA.
More of NPDA: |– denotes a move of NPDA.
PDA: Has (q, w, u),
where
q = cur rent state of autom a ton
w = unreal part of input string
u = stack con tents.
Simplifying CFG: Done either through (i) Empty Production removal (ii)
Unit production removal (iii) Left recursion removal.
DPDA: Deterministic PDA, which has a transition function as single-valued
for DFA and has λ-transitions.
Pumping Lemma: Theorem used to show that if certain strings belong to a
language, then certain other strings must also belong to the language.
Decision Algorithm: To find out if M accepts zero, a finite number, or an
infinite number of strings.
REVIEW QUESTIONS
1. Define a Pushdown automata.
2. Define a Nondeterministic Pushdown automata.
3. State the general form of transition function for an NPDA.
4. Give the instantaneous description of a PDA.
5. Explain how the strings are accepted with an NPDA.
6. What are the kinds of moves that can be made while accepting strings
with an NPDA?
7. Explain the terms (a) λ-transitions (b) Non-empty transitions
8. Give an example of NPDA execution.
9. State the relationship between PDA and context free languages.
10. Explain: (a) Empty Production removal (b) Unit Production removal.
11. What are the Normal forms of CFGs?
12. How will you convert a CFG to NPDA?
13. How will you convert a NPDA to CFG?
14. What do you mean by deterministic pushdown automata?
15. State the properties of Context free languages.
16. State the pumping lemma for CFG.
17. Give the proof for pumping lemma.
18. State the usuage of pumping lemma.
19. What are decision algorithms?
20. State the usefulness of decision algorithms.
180
Theory of Automata, Formal Languages and Computation