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

Q. Non-deterministic pushdown automaton that accepts the language generated by the grammar:

S→aSS | ab is

(A) δ(q0, λ, z) = { (q1, z)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, B) = { (q1, λ)},
δ(q1, λ, z) = { (qf, λ)}

(B) δ(q0, λ, z) = { (q1, Sz)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, B) = { (q1, λ)},
δ(q1, λ, z) = { (qf, λ)}

(C) δ(q0, λ, z) = { (q1, Sz)};
δ(q0, a, S) = { (q1, S)}, (q1, B) }
δ(q0, b, λ) = { (q1, B)},
δ(q1, λ, z) = { (qf, λ)}

(D) δ(q0, λ, z) = { (q1, z)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, λ) = { (q1, B)},
δ(q1, λ, z) = { (qf, λ)}

View solution

Q. Given L1 = L(a*baa*) and L2 = L(ab*)
The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by

View solution

Q. Given the production rules of a grammar G1 as

S1→AB | aaB
A→a | Aa
B→b

and the production rules of a grammar G2 as

S2→aS2bS2 | bS2aS2 | λ

Which of the following is correct statement?

View solution

Q. Given a grammar : S1→Sc, S→SA|A, A→aSb|ab, there is a rightmost derivation S1=>Sc =>SAC=>SaSbc. Thus, SaSbc is a right sentential form, and its handle is

View solution

Q. The equivalent production rules corresponding to the production rules

S→Sα1|Sα2|β1|β2 is

View solution