First order logic expression of "Each finite state automaton has an equivalent push-down automaton"? **Problem is** * * * > 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 represent the following? > > > Each finite state automaton has an equivalent pushdown automaton > * * * **I try to explain** * * * ∀x fsa(x)→(∃y pda(y)∧equivalent(x,y)) * * * It is given here (∀x fsa(x))→(∃y pda(y)∧equivalent(x,y)) * * * I have doubt is there typo or , is (∀x fsa(x))→(∃y pda(y)∧equivalent(x,y)) also true ?

In your second formula, x is not even bounded in the second part, so $$(∀x~ fsa(x))→(∃y~ pda(y)∧equivalent(x,y))$$ contains a free variable.

Even considering its universal closure, it would not mean what you want.