adplus-dvertising
frame-decoration

Question

Which of the following is not true?

a.

Power of deterministic automata is equivalent to power of non-deterministic automata.

b.

Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.

c.

Power of deterministic Turing machine is equivalent to power of non-deterministic Turing machine.

d.

All the above

Answer: (b).Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Which of the following is not true?

Similar Questions

Discover Related MCQs

Q. Identify the language which is not context - free.

Q. The context-free languages are closed for:

(i) Intersection                          (ii) Union
(iii) Complementation             (iv) Kleene Star

Q. Grammars that can be translated to DFAs:

Q. The language accepted by a Push down Automata:

Q. In parallel algorithm design, the process of grouping tasks into larger tasks in order to improve performance:

Q. Recursive Descent Parsers are a type of:

Q. If language L={0,1}*, then the reversed language L^R =

Q. Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.
Consider the following:

(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii) L(r) ⊆ L(s) and L(s) ⊆ L(t)

Choose the correct answer from given below:

Q. Consider the language L given by

L = {2^(nk) ∣ k>0, and n is non-negative integer number}

The minimum number of states of finite automaton which accepts the language L is

Q. The number of substrings that can be formed from string given by

a d e f b g h n m p

is

Q. Consider the following two languages:

L1 = {x ∣ for some y with ∣y∣ = 2^∣x∣,xy ∈ L and L is regular language}
L2 = {x ∣ for some y such that ∣x∣ = ∣y∣, xy ∈ L and L is regular language}

Which one of the following is correct?

Q. Consider the following languages:

L1 = {a^(n+m) b^n a^m ∣ n,m ≥ 0}
L2 = {a^(n+m) b^(n+m) a^(n+m) ∣ n,m ≥ 0}

Which of the following is correct?

Q. Consider R to be any regular language and L1, L2 be any two context-free languages. Which of the following is correct?

Q. Consider the following problems:

(i) Whether a finite state automaton halts on all inputs?
(ii) Whether a given context free language is regular?
(iii) Whether a Turing machine computes the product of two numbers?

Which one of the following is correct?

Q. Which of the following problems is decidable for recursive languages (L)?

Q. Consider the following grammar G:

S → A ∣ B
A → a ∣ c
B → b ∣ c
where {S, A, B} is the set of non-terminals, {a, b, c,} is the set of terminals.

Which of the following statement(s) is/are correct?
S1: LR(1) can parse all strings that are generated using grammar G.
S2: LL(1) can parse all strings that are generated using grammar G.

Q. The grammar S → (S) ∣ SS ∣ ϵ is not suitable for predictive parsing because the grammar is

Q. Two finite state machines are said to be equivalent if they:

Q. A pushdown automata behaves like a Turing machine when the number of auxiliary memory is:

Q. Pushdown automata can recognize language generated by ................