Chapter 6 --- Little Quiz   

 In each problem below, select an incorrect statement.                 

1. (a) CFL’s may be accepted by PDA’s.(b) A PDA is an epsilon-NFA with a stack.(c) More than one symbol may be popped up from the stack of a PDA in a state transition.(d) There are two different versions of PDA’s - accepting by final state and by empty stack.

2. (a) A PDA accepts strings generated by CFG’s.(b) A deterministic PDA (DPDA) has the same capability of language modeling as a nondeterministic PDA (NPDA).(c) The PDA has the same power of accepting CFL’s as that of the CFG for generating CFL’s.(d) NPDA’s accepts all and only CFL’s.

3. (a) A language accepted by an NPDA by empty stack can be accepted by another NPDA by final state.(b) A language accepted by an NPDA by final state can be accepted by another NPDA by empty stack.(c) An NPDA may be converted into an equivalent DPDA.(d) A DPDA is also an NPDA.

4. (a) A PDA accepting strings by empty stack may be described by a 6-tuple.(b) A PDA accepting strings by final state may be described by a 7-tuple.(c) Language {wcw’ | w is in L((0 + 1)*) and w’ is the reverse of w} can be accepted by a DPDA.(d) Languages accepted by NPDA’s are a subset of those accepted by DPDA’s.

5. (a) Languages accepted by DPDA’s by final state properly include RL’s, but are properly included in CFL’s.(b) If L is accepted by some DPDA P by empty stack, then L has an unambiguous CFG.(c) If L is accepted by some DPDA P by final state, then L has an unambiguous CFG.(d) Language {ww’ | w is in L((0 + 1)*) and w’ is the reverse of w} can be accepted by a DPDA.