The Gateway to Computer Science Excellence

NIELIT 2017 DEC Scientist B - Section B: 39

0 votes
32 views

Which of the following is true?

  1. Mealy and Moore machine are language acceptors.
  2. Finite State automata is language translator.
  3. NPDA is more powerful than DPDA.
  4. Mealy machine is more powerful than Moore machine.

NIELIT 2017 Scientist B - Section B-39

in Theory of Computation by Veteran
recategorized by | 32 views
0
The 4th option will be D) Mealy machine is more powerful than Moore machine.
0
(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.

6 Answers

+3 votes

Answer is C) NPDA is more powerful than DPDA

by Junior
+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)

by Boss
0
How can it accept or reject a language?  Mealy and Moore machines do not have final states. Please clarify.
+1 vote
NPDA is more powerful than DPDA. Therefore correct answer will be C
by
+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
by Active
+1
Other than the spelling mistakes, can you say why the other statements are not true?
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.

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

ago by Loyal

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
52,222 questions
59,848 answers
201,031 comments
118,094 users