Let fsa and pda be two predicates such that fsa(x) means x is a finite state…
GATE · 2008 · CSModified — slightly modified from the official paper; see the solution
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.
- A.
∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent(x, y)))
- B.
¬∀y (∃x fsa(x) ⇒ pda(y) ∧ equivalent(x, y))
- C.
∀x∃y (fsa(x) ∧ pda(y) ∧ equivalent(x, y))
- D.
∀x∃y (fsa(y) ∧ pda(x) ∧ equivalent(x, y))
Attempted by 122 students.
Sign up free to check your answer
Sign up freeLoading lesson…