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

View solution

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

View solution

Q. To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:

View solution

Q. Consider the following two Grammars:

G1 : S → SbS | a
G2 : S → aB | ab, A→GAB | a, B→ABb | b

Which of the following option is correct?

View solution

Q. Context sensitive language can be recognized by a:

View solution

Q. The set A={ 0^n 1^n 2^n | n=1, 2, 3, ......... } is an example of a grammar that is:

View solution

Q. A bottom-up parser generates:

View solution

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