edited by
13,842 views
70 votes
70 votes

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

  1. $\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)$
  2. $\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)$
  3. $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  4. $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$
edited by

5 Answers

Best answer
108 votes
108 votes
None of these.

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 an equivalent FSA.

The correct answer would be  

$\forall x \left(\text{fsa}\left(x\right)\implies \exists y \left( \text{pda}\left(y\right)\wedge \text{ equivalent}\left(x,y\right)\right)\right)$
edited by
3 votes
3 votes
This depicts even iit professors can commit mistakes :p
0 votes
0 votes

For x which is an fsa, there exists a y which is a pda and which is equivalent to x.

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

so option A is Correct.
 

Answer:

Related questions

3 votes
3 votes
3 answers
1
ParthPratim asked Nov 3, 2022
967 views
I have been trying to solve the question GATE CSE 2008 Question.Are the following two representations logically equivalent ?$\beta \rightarrow (\exists x, \alpha (x))$$\e...
37 votes
37 votes
11 answers
4