The Gateway to Computer Science Excellence

Redirected from merged question 335871
Close

0 votes

Which of the following is **true**?

- Mealy and Moore machine are language acceptors.
- Finite State automata is language translator.
- NPDA is more powerful than DPDA.
- Mealy machine is more powerful than Moore machine.

+3 votes

(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)**

+1 vote

$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

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

0 votes

**Mealy and Moore machines are language acceptors.**

→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.

→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.

→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.

Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.

0 votes

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

2. Finite State automata is language translator. **FALSE**

becasue Finite State automata cannot translate a language into another.

3. NPDA is more powerful than DPDA. **TRUE**

4. Mealy machine is more powerful than Moore machine. **FALSE**

** because mealy and moore machine have equal power.**

**Hence option A and C is correct.**

52,222 questions

59,848 answers

201,031 comments

118,094 users