Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{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
- $\left(\forall x \text{ fsa}\left(x\right) \right) \implies \left( \exists y \text{ pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
- $\neg \forall y \left(\exists x \text{ fsa}\left(x\right) \implies \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
- $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
- $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$