adplus-dvertising
frame-decoration

Question

Consider the following statements:

S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.

Which of the following options is correct?

a.

Both S1 and S2 are correct

b.

Both S1 and S2 are not correct

c.

Only S1 is correct

d.

Only S2 is correct

Answer: (a).Both S1 and S2 are correct

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Consider the following statements: S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language. S2 : The problem of determining...

Similar Questions

Discover Related MCQs

Q. Given the following expressions of a grammar

E --> E * F / F + E / F
F --> F - F / id

Which of the following is true ?

Q. Which of the following is true while converting CFG to LL(1) grammar ?

Q. Let L be a set accepted by a non deterministic finite automaton. The number of states in non-deterministic finite automaton is |Q|. The maximum number of states in equivalent finite automaton that accepts L is

Q. The grammar ‘G1’

S ---> OSO| ISI | 0|1|∈

and the grammar  ‘G2’ is
S ---> as |asb| X,
X -----> Xa | a.

Which is the correct statement ?

Q. Which of the following regular expression identities are true ?

Q. The minimum number of states of the non-deterministic finite automation which accepts the language
{a b a bn| n  ≥  0} ∪ {a b an|n  ≥ 0} is 

Q. Which of the following definitions generates the same Language as L, where
L = {WWR | W ∈ {a, b}*} 

Q. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length 

Q. Given the following statements :

S1: SLR uses follow information to guide reductions.In case of LR and LALR parsers, the look-aheads are associated with the  Items and they make use of the left context available to the parser.
S2: LR grammar is a larger sub-class of context free grammar as compared to that SLR and LALR grammars. 

Which of the following is true ? 

Q. The context free grammar for the language

L= {anbm  | n ≤ m+3,n ≥ 0 ,m≥ 0 } : is

Q. Given the following statements:

S1: If L is a regular language then the language {uv | u ∈  L, v ∈ LR } is also regular.
S2: L = {wwR} is regular language.

Which of the following is true?

Q. Given the following statements.

S1: The grammars S → asb | bsa |ss I a and s→ asb | bsa| a are not equivalent.
S2: The grammars S→. ss| sss | asb | bsa| λ and S → ss |asb |bsa| λ are equivalent.

Which of the following is true?

Q. Pumping -lemma for context-free languages states :
Let Lbe an infinite context free language. Then there exists some positive integer m such that any w ∈ L with Iwl ≥m can be decomposed as w = uv xy Z with Ivxyl_________ and Ivy I such that uvz, xyZ
Z ∈ L for all z = 0, 1,2, .......

Q. The Greibach normal form grammar for the language L = {an bn+1 | n ≥ 0 } is

Q. Given the following statements:

S1: Every context-sensitive language L is recursive.
S2: There exists a recursive language that is not context sensitive.

Which statement is correct?

Q. Shift-Reduce parsers perform the following :

Q. The following Context-Free Grammar (CFG) :

S → aB | bA

A → a | as | bAA

B → b | bs | aBB

will generate

Q. Which of the following is true?

Q. The pushdown automation M = ( {q0, q1, q2}',{a, b}, {0, 1}, δ, q0,0, {q0}) with

δ (q0, a, 0) = {(q1,10)}

δ (q1,a, 1) = {(q1,11)}

δ (q1,b, 1) = {(q2 , λ)}

δ(q2 , b, 1) = {(q2 , λ)}

δ (q2 , A, 0) = {(q0, λ)}

Accepts the language

Q. Given two languages:

L1= {(ab)n,ak I n> k, k >=0}

L2 = {an bm l n ≠ m}

Using pumping lemma for regular language, it can be shown that