KANIMOZHIK

  Unit-IV Pushdown Automata , CFL And NCFL Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL. 4.1)Pushdown Automata ·        The  pushdown automaton  is in essence a  nondeterministic finite automata  with ε-moves permitted and one additional stack capability on which it can store a string of “stack symbols”. ·        The presence of a stack means that, unlike the finite automaton, the pushdown automaton can remember an infinite amount of information. ·        However, unlike a general-purpose computer, which also has the ability to remember arbitrarily large amount of information, the pushdown automaton can only access the information on its stack in a LIFO (last-in-first-out) way. ·        There are languages that could be recognized by...