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 whether a Turing machine halts on any input is undecidable.

Which of the following options is correct?

View solution

Q. Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non-negative decimal values, does not include even values? (Where {+, *} are quantification characters.)

View solution

Q. Which of the following statements is/ are TRUE?

(a) The grammar S → SS a is ambiguous. (Where S is the start symbol)
(b) The grammar S → 0S1 | 01S | ϵ is ambiguous. (The special symbol ϵ represents the empty string) (Where S is the start symbol)
(c) The grammar (Where S is the start symbol)
S → T/U
T → x S y | xy | ϵ
U → yT
generates a language consisting of the string yxxyy.

View solution

Q. Pumping lemma for regular language is generally used for proving:

View solution

Q. Which of the following problems is undecidable?

View solution

Q. Finite state machine can recognize language generated by ....................

View solution

Q. The language L = {a^i b c^i | i ≥ 0} over the alphabet {a, b, c} is:

View solution

Q. Which of the following statements is not correct?

View solution

Q. Context free grammar is not closed under :

View solution

Q. Consider the following languages :

L1 = {a^m b^n | m ≠ n}
L2 = {a^m b^n | m = 2n+1}
L3 = {a^m b^n | m ≠ 2n}

Which one of the following statement is correct?

View solution