edited by
398 views
0 votes
0 votes

Statement 1 : For push down automata Determinism ≠ Non-determinism

Statement 2 : For Finite Automata Non-determinism = Determinism

Which of the following is correct?

  1. Both statements are true.
  2. Both statements are false.
  3. Statement 1 is true and Statement 2 is false
  4. Statement 1 is false and Statement 2 is true
edited by

2 Answers

0 votes
0 votes

The languages accepted by NPDA (Non-Deterministic Push Down Automata) are not accepted by DPDA (Deterministic Push Down Automata)

But, the languages accepted by DPDA are accepted by NPDA.

NPDA is a superset of DPDA

and hence, NPDA is more powerful than DPDA.

Statement 1 is true.

Now, in case of FA (Finite Automata), we know that an NFA (Non-Deterministic Finite Automata) can be converted to an DFA (Deterministic Finite Automata).

& an DFA can be converted to NFA.

So, DFA ≅ NFA

Statement 2 is also true.

Option a) Both statements are true will be the answer.

edited by

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Mar 2, 2018
294 views
The total number of words represented by the regular expression (^ + a + b) (^ + a + b) (^ + a + b) is815169
1 votes
1 votes
2 answers
2
gatecse asked Mar 2, 2018
979 views
A turing machine crashesIf the machine reads all the input characters without traversing some state.If the machine traverses all its states till the input remainsIf the t...
1 votes
1 votes
1 answer
3
0 votes
0 votes
2 answers
4
gatecse asked Mar 2, 2018
737 views
Bluetooth uses ____ method in physical layer to avoid interference from other devices or other networksFHSSFDSSTDSNone of the above