134k views
5 votes
A language L is deterministic context-free if and only if there is a deterministic push-down automaton M such that L = L(M).

false
true

User Foobrew
by
8.2k points

1 Answer

7 votes

Final answer:

A language L is indeed deterministic context-free if there exists a deterministic push-down automaton M such that L equals the language accepted by M. The given statement is true.

Step-by-step explanation:

The statement that a language L is deterministic context-free if and only if there is a deterministic push-down automaton (M) such that L = L(M) is true. A deterministic context-free language is defined by the property that it can be accepted by a deterministic push-down automaton. Such an automaton has the characteristic that for any given state and input symbol (including the empty string), there is at most one action to be taken, meaning that its computation is deterministic and there is no need for guesswork or backtracking.

User Alexander Bily
by
8.6k points