Which one of the following statements is FALSE?

Answer (False statement): The statement "Both deterministic and non-deterministic pushdown automata always accept the same set of languages" is false.

Reason:

• Deterministic pushdown automata accept deterministic context-free languages (DCFLs), while nondeterministic pushdown automata accept all context-free languages (CFLs).

• The class of deterministic context-free languages is strictly contained in the class of context-free languages; therefore the two types of PDAs do not accept the same set of languages.

• A useful formal justification is via closure properties: deterministic context-free languages are closed under complement, whereas context-free languages in general are not; this implies the classes differ.

Brief notes on the other statements:

• There do exist inherently ambiguous context-free languages (so the statement that such languages exist is true).

• An unambiguous context-free grammar does guarantee a unique parse tree for each string it generates (this property is about the grammar itself).

• Any finite set of strings over an alphabet is regular: you can construct a finite automaton or a regular expression that accepts exactly those strings.