Q. Match the following :

List - I                                                             List - II
(a) {a^n b^n|n > 0} is a deterministic                  (i) but not recursive language
context free language        
(b) The complement of {a^n b^n a^n|n > 0}         (ii) but not context free language
is a context free language
(c) {a^n b^n a^n} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation
(d) L is a recursive language                         (iv) but not regular

Codes :
     (a)   (b)   (c)   (d)

View solution

Q. The language of all non-null strings of a’s can be defined by a context free grammar as
follow :

S→a S|S a| a

The word a^3 can be generated by ................ different trees.

View solution

Q. The context free grammar given by

S→XYX
X→aX|bX|λ
Y→bbb

generates the language which is defined by regular expression:

View solution

Q. There are exactly ................ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.

View solution

Q. Given the following two languages :

L1={a^n b a^n|n>0}
L2={a^n b a^n b^n+1|n>0}

Which of the following is correct?

View solution

Q. Consider a language A defined over the alphabet ∑={0, 1} as A = {0^[n/2] 1^n: n >= 0} .
The expression [n/2] means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.

Which of the following is not an example of a string in A ?

View solution

Q. A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β

I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)

View solution

Q. A shift reduce parser suffers from

View solution

Q. The context free grammar for language L = {a^nb^mc^k | k = |n - m|, n≥0,m≥0,k≥0} is

View solution

Q. The number of states in a minimal deterministic finite automaton corresponding to the language L = { an | n≥4 } is

View solution

Q. Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is

View solution

Q. Consider the following two languages:

L1 = {a^n b^l a^k | n + l +k>5 }
L2 = {a^n b^l a^k |n>5, l >3, k≤ l }

Which of the following is true?

View solution

Q. LL grammar for the language L = {a^n b^m c^n+m | m≥0, n≥0} is

View solution

Q. Assume the statements S1 and S2 given as:

S1: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.
S2: There exists an algorithm to determine whether two context free grammars generate the same language.

Which of the following is true?

View solution

Q. Assume, L is regular language. Let statements S1 and S2 be defined as :

S1 : SQRT(L) = { x| for some y with |y| = |x|^2, xy ∈L}
S2 : LOG(L) = { x| for some y with |y| = 2^|x|, xy ∈ L}

Which of the following is true ?

View solution

Q. A regular grammar for the language L = {a^nb^m | n is even and m is even}is given by

View solution

Q. Given the following productions of a grammar :

S→ aA| aBB;
A→aaA |λ ;
B→ bB| bbC;
C→ B

Which of the following is true ?

View solution

Q. The language accepted by the nondeterministic pushdown automaton

M= ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with transitions
δ (q0 a, z) = { (q1 a), (q2 λ)};
δ (q1, b, a) = { (q1, b)}
δ (q1, b, b) ={ (q1 b)}, δ (q1, a, b) = { (q2, λ)}

is

View solution

Q. The language L = {a^n b^n a^m b^m | n ≥ 0, m ≥ 0} is

View solution

Q. Assume statements S1 and S2 defined as :

S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.
S2 : The set of all Turing machines is countable.

Which of the following is true ?

View solution