Grammar
Question 1 
aaaabb
 
aabbbb
 
aabbab  
abbbba 
Question 1 Explanation:
The string “aabbab” can be derived by following steps:
S > aB [Using S > aB]
> aaBB [Using B > aBB]
> aabB [Using B > b]
> aabbS [Using B > bS]
> aabbaB [Using S > aB]
> aabbab [Using B > b]
S > aB [Using S > aB]
> aaBB [Using B > aBB]
> aabB [Using B > b]
> aabbS [Using B > bS]
> aabbaB [Using S > aB]
> aabbab [Using B > b]
Question 2 
1  
2  
3  
4 
Question 2 Explanation:
There exist two parse tree for the string “aabbab” using LMD (left most derivation)
Question 3 
Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
L (D) ⊂ L (G)  
L (D) ⊃ L (G)  
L (D) = L (G)  
L (D) is empty 
Question 3 Explanation:
By changing the corresponding grammar, the language will not be changed.
For example, by converting NFA to DFA language will not be changed.
For example, by converting NFA to DFA language will not be changed.
Question 4 
G1 : No y appears before any x G2 : Every x is followed by at least one y  
G1 : No y appears before any x G2 : No x appears before any y  
G1 : No y appears after any x G2 : Every x is followed by at least one y  
G1 : No y appears after any x G2 : Every y is followed by at least one x 
Question 4 Explanation:
Regular expression for G1:
(x + z)* + (x + z)* y(y + z)*
Regular expression for G2:
(y + z + xy)*
(x + z)* + (x + z)* y(y + z)*
Regular expression for G2:
(y + z + xy)*
Question 5 
(i), (ii), and (iii)  
(ii), (v), and (vi)  
(ii), (iii), and (iv)  
(i), (iii), and (iv) 
Question 5 Explanation:
(ii) xxyyxy
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy
(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy
(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy
(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy
(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy
Question 6 
In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string a^{l}b^{m} with l≠m?
max(l,m)+2  
l+m+2
 
l+m+3
 
max(l, m)+3

Question 6 Explanation:
The correct grammar for L = {a^{i}b^{j}  i≠j} is
S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2
S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2
Question 7 
Which one of the following grammars generates the language L = {a^{i}b^{j}  i≠j}?
S→ACCB C→aCbab A→aAϵ B→Bbϵ  
S→aSSbab
 
S→ACCB C→aCbϵ A→aAϵ B→Bbϵ  
S→ACCB C→aCbϵ A→aAa B→Bbb 
Question 7 Explanation:
The language have all the strings in which a’s comes before b’s and number of a’s never equal to b’s. The grammars in Option A, B and C generates string “ab” in which number of a’s are equal to b’s, hence they are wrong. But option D generates all the string which is in L.
Question 8 
n, E + n and E + n × n
 
n, E + n and E + E × n
 
n, n + n and n + n × n
 
n, E + n and E × n

Question 8 Explanation:
E → E + n {Applying E → E+n}
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 9 
200  
180  
160  
40 
Question 9 Explanation:
Given expression is
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
Question 10 
{wN_{a}(w) > 3N_{b}(w)}
 
{wN_{b}(w) > 3N_{a}(w)}  
{wN_{a}(w) = 3k, k Î {0, 1, 2, ...}}
 
{wN_{b}(w) = 3k, k Î {0, 1, 2, ...}}

Question 10 Explanation:
S→bS
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
N_{a}(w) > 3N_{b}(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
N_{b}(w) > 3N_{b}(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
N_{b}(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
n(a)=3
→ Answer: Option C(✔️)
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
N_{a}(w) > 3N_{b}(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
N_{b}(w) > 3N_{b}(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
N_{b}(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
n(a)=3
→ Answer: Option C(✔️)
Question 11 
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
Removing left recursion alone
 
Factoring the grammar alone  
Removing left recursion and factoring the grammar  
None of the above 
Question 11 Explanation:
Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 12 
* has higher precedence than +  
 has higher precedence than *  
+ and – have same precedence  
+ has higher precedence than * 
Question 12 Explanation:
The operator which is in low level that can have high preference.
Order of precedence is *, +, .
Here * and + have equal preference, '' can have higher precedence than + and *.
Order of precedence is *, +, .
Here * and + have equal preference, '' can have higher precedence than + and *.
Question 13 
A grammar that is both left and right recursive for a nonterminal, is
Ambiguous  
Unambiguous  
Information is not sufficient to decide whether it is ambiguous or unambiguous  
None of the above 
Question 13 Explanation:
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 14 
‘⊕’ is left associative while ‘*’ is right associative  
Both ‘⊕’ and ‘*’ is left associative  
‘⊕’ is right associative while ‘*’ is left associative  
None of the above 
Question 14 Explanation:
⊕ is left associative.
* is right associative.
Question 15 
Which of the following conversions is not possible (algorithmically)?
Regular grammar to context free grammar  
Nondeterministic FSA to deterministic FSA  
Nondeterministic PDA to deterministic PDA  
Nondeterministic Turing machine to deterministic Turing machine 
Question 15 Explanation:
NPDA to DPDA conversion is not possible. They have different powers.
There are 16 questions to complete.