Test: From Grammars to Push Down Automata - Computer Science Engineering (CSE) MCQ

 A->ε is termed as Null production while A->B is termed as Unit production.

 Halting states are the new tuple members introduced in turing machine and is of two types: Accept Halting State and Reject Halting State.

z0 is the initial stack symbol, is an element of G. Other symbols like d represents the transition function of the machine.

Using this notation, we can define moves and further acceptance of a string by the machine.

If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty, since R∈L. But then T cannot be accepted, since M cant move with an empty stack.

Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.

:The possible change in the stack contents is a change in the number of A’s on the stack.

The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.

A string is said to be balanced if it consist of equal number of 0’s and 1’s.