NIELIT 2017 DEC Scientist B - Section B: 39

Question

Which of the following is true?

• A. Mealy and Moore machine are language acceptors.
• B. Finite State automata is language translator.
• C. NPDA is more powerful than DPDA.
• D. Melay machine is more powerful than Moore machine.

Comments

The 4th option will be D) Mealy machine is more powerful than Moore machine.

---

(A) Mealy and Moore machine are language acceptors TRUE

      because Mealy and Moore both are finite state machines.So. both of them are accepting some language.

---

both A and C are correct.

---

So what is the exact answer? A and C or only C?

Answer 1

Answer is C) NPDA is more powerful than DPDA

Answer 2

(A) Mealy and Moore machine are language acceptors. TRUE
       because Mealy and Moore both are finite state machines.So. both of them are accepting some language.

(B) Finite State automata is language translator. FALSE

      Finite State automata cannot translate a language into another.

(C) NPDA is more powerful than DPDA. TRUE

D) Mealy machine is more powerful than Moore machine.  FALSE

So, the answer will be both A) & C)

Comments

How can it accept or reject a language?  Mealy and Moore machines do not have final states. Please clarify.

---

Mealy and Moore machines are not language acceptors. They produce output based on input and/or state using actions. They are categoried under Transducers. Language acceptors are separate classification under FSM. Only option (C) is true.

Source: https://en.wikipedia.org/wiki/Finite-state_machine#Acceptors

Answer 3

NPDA is more powerful than DPDA. Therefore correct answer will be C

Answer 4

$C$ is correct .

There exist some context-free languages for which it is not possible to construct a DPDA whereas a NPDA can be easily constructed,

Example: Set of all even length palindromes over an alphabet i.e. $L=\left \{ ww^{R} \right \}$ .Here, it is not possible to find the centre of the string deterministically and hence NPDA is used to recognize strings of this language.

This implies NPDA is more powerful than DPDA

Comments

Other than the spelling mistakes, can you say why the other statements are not true?