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)$

### 6 Comments

@Arjun sir Does it means There exist atleast one PDA for every FSA.

Also can we Say option A and Option C are interpreting the same meaning

## 4 Answers

A. If everything is a FSA, then there exists an equivalent PDA for everything.

B. It is not the case that for all y if there exist a FSA then it has an equivalent PDA.

C. Everything is a FSA and has an equivalent PDA.

D. Everything is a PDA and has exist an equivalent FSA.

The correct answer would be

$\forall x \left(\text{fsa}\left(x\right)\implies \left(\exists y \text{ pda}\left(y\right)\wedge \text{ equivalent}\left(x,y\right)\right)\right)$

### 21 Comments

@Warrior , I think

we can take out "there exist y" out of the expression, but it should be after "for all x", it should not come before "for all x".

@Arjun converted option A into english sentence. My doubt is if the scope of x is not defined while we are on RHS then how can we interpret it.

@ Arjun Sir in your corrected answer, if we don't use parenthesis after "∃y" than won't its scope be limited to pda(y) only?

@Arjun sir, as @ankitgupta.1729 mentioned in the comments, shouldn't∃y be outside the parenthesis as the scope extends to *equivalent *predicate as well. Or is it implicit?

@Arjun Sir , Shouldn't the correct answer be

∀x(fsa(x)⟹∃y (pda(y)∧ equivalent(x,y)))

According to me , parenthesis is after ∃y