in Mathematical Logic edited by
9,387 views
58 votes
58 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
9.4k views

4 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 

0
0

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.

1
1
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

4 Answers

89 votes
89 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

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).
0
0

@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
2 votes
2 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 🙂
6
6
kitne tejasvi log hain hamre pass 😂
0
0
1 vote
1 vote
Confused in A and C :(
–3 votes
–3 votes
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

1 comment

15
15
Answer:

Related questions