The GATE Grind

GATE 2008 CS – Question 30

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

fsa(x) means x is a finite-state automaton; pda(y) means y is a pushdown automaton; equivalent(a, b) means language equivalence. Which formula expresses “Each finite-state automaton has an equivalent pushdown automaton”?

  1. $\forall x\,[fsa(x)\Rightarrow\exists y(pda(y)\land equivalent(x,y))]$
  2. $\forall y\,[\exists x\,fsa(x)\Rightarrow pda(y)\land equivalent(x,y)]$
  3. $\forall x\exists y(fsa(x)\land pda(y)\land equivalent(x,y))$
  4. $\forall x\exists y(fsa(y)\land pda(x)\land equivalent(x,y))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\forall x\,[fsa(x)\Rightarrow\exists y(pda(y)\land equivalent(x,y))]$

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Discrete Mathematics: Propositional and First Order Logic questions

All Discrete Mathematics: Propositional and First Order Logic questions →