The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 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)$
asked in Mathematical Logic by Veteran (59.9k points)
edited by | 3.1k views
Can you please translate c into English
It means everything is a FSA and there exist an equivalent PDA for each of them.
Thank you.It helped me a lot
Is it the case that the chosen logical statement should be a tautology?

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

3 Answers

+50 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)$
answered by Veteran (384k points)
edited by
@Omesh-pandita can you please verify?
Why option A is not the answer?

x (fsa(x)(y pda(y)equivalent(x,y)))

This is true. But the parenthesis in A is wrong. The LHS in A says "if every x is a fsa"

@Arjun Suresh : What is the meaning of the Correct answer you posted at last. I mean difference in English meaning of the Correct Answer and the Option A.
Can correct form also be written like this:- 1

∀x(fsa(x)$\rightarrow$  (∃y( pda(y) ∧ equivalent(x, y))))

Or like this:-2

∀x∃y(fsa(x)$\rightarrow$  ( pda(y) ∧ equivalent(x, y)))
If domain of x is universal set of FSA only and not universal set of all Automaton then A) is correct?
Thanx Arjun sir. This solution cleared many doubts.
@Arjun sir,.In the first option the scope of x will be finished by the time we are on RHS?
Option C also looking correct one but it contain x as universal set fsa will be finite always.
How option A is different from your answer as scope of universal quantifier doesn't changed in both.

And option A couldn't be translated as

"For everything in universe If , it is a fsa then......"?
(∀x fsa(x)) means Everything is FSA.
Yes,Thanks now i understood after further reading the binding of quantifiers

How '(' or a " , " after quantifier can change its binding scope to the predicate function at R.H.S
how c option is implying everything is fsa

It can also written as   ∀x∃y [fsa(x)⟹( pda(y)∧ equivalent(x,y))] .Is not it?


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.

great solution
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.

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

@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.
What is the negation of option B?

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


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?

Yes for every x fsa(x) mean everything is fsa here
@Arjun Sir, I also think that $\exists y$ should be outside the parenthesis. Please correct me If I am wrong.
Thq soo much sir....

@ankitgupta.1729 yes you are right..

0 votes
This depicts even iit professors can commit mistakes :p
answered by Junior (773 points)
–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
answered by Active (4.7k points)

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
47,922 questions
52,324 answers
67,780 users