Let fsa and pda be two predicates such that fsa(x) means x is a finite state…
2008
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following:
Each finite state automaton has an equivalent pushdown automaton.
Attempted by 35 students.
Show answer & explanation
Correct translation: ∀x ( fsa(x) ⇒ ∃y ( pda(y) ∧ equivalent(x,y) ) )
Plain English: For every object x, if x is a finite state automaton then there exists an object y that is a pushdown automaton and y is equivalent to x.
Key points:
The universal quantifier applies to x (every candidate machine).
The implication means the existence requirement applies only when x is an fsa (not for arbitrary domain elements).
The existential quantifier for y is inside the implication, so the pda may depend on the particular fsa x.
Why other formalizations are incorrect:
A formula that puts fsa(x) inside the existential conjunction (e.g. ∀x ∃y (fsa(x) ∧ pda(y) ∧ equivalent(x,y))) wrongly forces every x in the domain to be an fsa, which is stronger than intended.
A formula that swaps x and y so that x is required to be a pda and y an fsa expresses the reverse claim (each pda has an equivalent fsa), not the given statement.
Introducing a negation or moving quantifiers so that the existence of the pda is not tied to the particular fsa changes the dependency and yields a statement with a different meaning.
A video solution is available for this question — log in and enroll to watch it.