in Mathematical Logic edited by
13,810 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)$
in Mathematical Logic edited by
13.8k views

4 Comments

How can we have option (b) using variable y in it's english equivalent...while no other option uses these free variable for the same. It ain't the case that x and y are necessarily bound to FSA and PDA respectively.

We need to first define the domain for variable x  and y .

Or as per the given defination of "FSA(x)" and PDA (y) , everything that is supplied to FSA becomes FSA  and same for PDA. Then following that option (a) must be correct.
0
0

@Oaesp

FSA(x): “ $x$ is a finite state automaton” 

PDA(y): “$y$ is a push down automation”

Domain here is whole universe.

As far as i can see option $b$ has no free variables but option $a$ does have a free variable.

0
0
edited by

$\color{red}{\text{Detailed Video Solution:}}$ Detailed Video Solution with Complete Analysis

Note (ALL the following points have been explained in the Above Video Solution ):

1. Option A has Free Variables $x,y$ So, it is not even a proposition. Explained HERE & HERE.

2. No option is correct But during the GATE exam, during those 3 hours, Do Not Leave such question even if you think that it would be Marks to all. Choose the Closest option among all. Like, for this question, Option A should be chosen ( Watch this to know WHY!! )

8
8

5 Answers

108 votes
108 votes
Best answer
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
by

4 Comments

@Arjun @Deepak Poonia sir i think @Gaganjot _Kaur is correct

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

Sir I think this is the correct answer.

2
2
If we consider the domain of discourse to be set of PDAs will option d be correct?
0
0

@Arjun Sir, The translation of option A is incorrect. Expression in option A has FREE variables $x,y.$ So, the correct translation of option A will be a sentence about $x,y$ given below:

If everything is a FSA, then there is some PDA & $x$ is equivalence to $y$.

This is a predicate over variables $x,y.$ So, we can write it as $P(x,y).$

Can check out this comment as well:

https://gateoverflow.in/441/gate-cse-2008-question-30?show=404943#c404943 

3
3
3 votes
3 votes
This depicts even iit professors can commit mistakes :p

3 Comments

They are too humans 😂.

Every human can commit mistake 

V ( Human(X)  /\ Mistake(X.Y) )

 

2
2
i think /\ should be replaced with --> 😅

please correct me if I am wrong 🙂
10
10
kitne tejasvi log hain hamre pass 😂
1
1
1 vote
1 vote
Confused in A and C :(
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.
 

4 Comments

Wrong Answer, Read the first option correctly and check the parentheses.
0
0
answer is correct

read statement

Each finite state automaton has an equivalent pushdown automaton

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

and compare this statement with other options

according to this option A is correct

hope u get it

and message me if i m wrong
0
0
your answer is not there in option,see the brackets carefully
1
1

option A is different from your answer. In option A, x in the inplied part is not even dependent on left side x

0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true