Which of the following pairs have DIFFERENT expressive power...

MCQ

Which of the following pairs have DIFFERENT expressive power?

Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)

Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

Single-tape Turing machine and multi-tape Turing machine

Community Discussion

No discussions yet. Be the first to start!

You must be logged in to participate in the discussion.

Similar Questions

MCQ

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S ? a S b | SS | ? Which of the following statements is true?

G is not ambiguous

There exist x, y, ? L (G) such that xy ? L(G)

There is a deterministic pushdown automaton that accepts L(G)

We can find a deterministic finite state automaton that accepts L(G)

Discussion

MCQ

Consider the languages:

L1 = {wwR |w ? {0, 1}*}
L2 = {w#wR | w ? {0, 1}*}, where # is a special symbol
L3 = {ww |  w ?  (0, 1}*)

Which one of the following is TRUE?

L1 is a deterministic CFL

L2 is a deterministic CFL

L3 is a CFL, but not a deterministic CFL

L3 is a deterministic CFL

Discussion

MCQ

Which of the following statement is false?

Context free language is the subset of context sensitive language

Regular language is the subset of context sensitive language

Recursively ennumerable language is the super set of regular language

Context sensitive language is a subset of context free language

Discussion

MCQ

Given the following two languages: L1 = {anban|n > 0} L2 = {an b an bn + 1|n > 0} Which of the following is correct ?

L₁ is context free language and L₂ is not context free language

L₁ is not context free language and L₂ is context free language

Both L₁ and L₂ are context free languages

Both L₁ and L₂ are not context free languages

Discussion

MCQ

Consider the following statements about the context free grammar G = {S-->SS , S-->ab , S-->ba , S-->^} I. G is ambiguous II. G produces all strings with equal number of a

I only

I and III only

II and III only

I, II and III

Discussion

Banking

Engineering

General

Medical

Question Discussion & Solution

Report Error

Community Discussion

Similar Questions

Report Error

Report Error

Report Error

Report Error

Report Error

More Theory of Automata Topics

Reqular Expressions

Finite Automata

Context Free Grammars

Push Down Automata

Regular and context free languages

Pumping Lemma

Turning Machine

Banking

Engineering

General

Medical

Question Discussion & Solution

report Report Error

forum Community Discussion

auto_awesome Similar Questions

report Report Error

report Report Error

report Report Error

report Report Error

report Report Error

category More Theory of Automata Topics

Reqular Expressions

Finite Automata

Context Free Grammars

Push Down Automata

Regular and context free languages

Pumping Lemma

Turning Machine

Report Error

Community Discussion

Similar Questions

Report Error

Report Error

Report Error

Report Error

Report Error

More Theory of Automata Topics