The Gateway to Computer Science Excellence

+44 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

- $\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)$
- $\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)$
- $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
- $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$

0

@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

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

The correct answer would be

$\forall x \left(\text{fsa}\left(x\right)\implies \left(\exists y \text{ pda}\left(y\right)\wedge \text{ equivalent}\left(x,y\right)\right)\right)$

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

The correct answer would be

$\forall x \left(\text{fsa}\left(x\right)\implies \left(\exists y \text{ pda}\left(y\right)\wedge \text{ equivalent}\left(x,y\right)\right)\right)$

0

How both(given below) are equivalent to ∀x(fsa(x)⟹(∃y pda(y)∧ equivalent(x,y))).

- ∀x(fsa(x)→ (∃y( pda(y) ∧ equivalent(x, y))))
- ∀x∃y(fsa(x)→ ( pda(y) ∧ equivalent(x, y)))

I did not getting.Plz verify me.

0

Is it possible to interpret above correct answer in following manner:

1. Every FSA has some equivalent PDA

2. If each x is a FSA then there exists Atleast one equivalent PDA for it.

1. Every FSA has some equivalent PDA

2. If each x is a FSA then there exists Atleast one equivalent PDA for it.

+1

@Warrior , I think

we can take out "there exist y" out of the expression, but it should be after "for all x", it should not come before "for all x".

0

@rahul sharma I too think that the scope of x will be finished by the time we reach RHS. And if this is the case then the option doesnt make any sense. So how can you convert such sentences to english.

@Arjun converted option A into english sentence. My doubt is if the scope of x is not defined while we are on RHS then how can we interpret it.

@Arjun converted option A into english sentence. My doubt is if the scope of x is not defined while we are on RHS then how can we interpret it.

+1

Arjun sir is right because simple thing is here **scope **of x is different from both sides...

once we complete LHS then from RHS, x is free variable so we can take it any value..

Refer Kenneth. H Rosen for the same...

+2

@ Arjun Sir in your corrected answer, if we don't use parenthesis after "∃y" than won't its scope be limited to pda(y) only?

+3

@Arjun Sir, I also think that $\exists y$ should be outside the parenthesis. Please correct me If I am wrong.

0

@khushtak After Implies(→) symbol , is that the negation symbol in both 1 and 2?

If yes then what will be there english conversion considering the negation?

If yes then what will be there english conversion considering the negation?

0

@Arjun sir, as @ankitgupta.1729 mentioned in the comments, shouldn't∃y be outside the parenthesis as the scope extends to *equivalent *predicate as well. Or is it implicit?

+1

@Arjun Sir , Shouldn't the correct answer be

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

According to me , parenthesis is after ∃y

52,345 questions

60,469 answers

201,795 comments

95,272 users