9,387 views

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

@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

Meanings of A and C are also different. Option C says that " everything  is a fsa and there exist an equivalent pda for each of them". (As arjun sir already describes the meaning of C). And option A is if then statement.

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.

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.

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

The framing of this question have some seriously flaws. It reminds me of flawed SET DEFINITION that couldn't justify the set of "Set of all sets that are not part of any set".

As per question definitions the answer must be (a).

@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.

If we consider the domain of discourse to be set of PDAs will option d be correct?
This depicts even iit professors can commit mistakes :p
by

They are too humans 😂.

Every human can commit mistake

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

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

please correct me if I am wrong 🙂
kitne tejasvi log hain hamre pass 😂
Confused in A and C :(
Let a and b be two proposition
a: Good Mobile phones.
b: Cheap Mobile Phones.

P and Q can be written in logic as
P: a-->~b
Q: b-->~a.

Truth Table
a   b   ~a  ~b   P   Q
T   T   F    F   F   F
T   F   F    T   T   T
F   T   T    F   T   T
F   F   T    T   T   T

it clearly shows P and Q are equivalent.
so option D is Correct
by