Grammar

Question 1
 
A
aaaabb
B
aabbbb
C
aabbab
D
abbbba
       Compiler-Design       Grammar       Gate-2007
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]
Question 2
A
1
B
2
C
3
D
4
       Compiler-Design       Grammar       Gate-2007
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 ?
A
L (D) ⊂ L (G)
B
L (D) ⊃ L (G)
C
L (D) = L (G)
D
L (D) is empty
       Compiler-Design       Grammar       Gate 2007-IT
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.
Question 4
 
A
G1 : No y appears before any x
G2 : Every x is followed by at least one y
B
G1 : No y appears before any x
G2 : No x appears before any y
C
G1 : No y appears after any x
G2 : Every x is followed by at least one y
D
G1 : No y appears after any x
G2 : Every y is followed by at least one x
       Theory-of-Computation        Grammar       Gate 2007-IT
Question 4 Explanation: 
Regular expression for G1:
(x + z)* + (x + z)* y(y + z)*
Regular expression for G2:
(y + z + xy)*
Question 5
 
A
(i), (ii), and (iii)
B
(ii), (v), and (vi)
C
(ii), (iii), and (iv)
D
(i), (iii), and (iv)
       Theory-of-Computation       Grammar       Gate 2007-IT
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
Question 6
Which one of the following grammars generates the language L = {aibj | i≠j}?
A
S→AC|CB
C→aCb|a|b
A→aA|ϵ
B→Bb|ϵ
B
S→aS|Sb|a|b
C
S→AC|CB
C→aCb|ϵ
A→aA|ϵ
B→Bb|ϵ
D
S→AC|CB
C→aCb|ϵ
A→aA|a
B→Bb|b
       Theory-of-Computation       Grammar       Gate-2006
Question 6 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 7
In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string albm with l≠m?
A
max(l,m)+2
B
l+m+2
C
l+m+3
D
max(l, m)+3
       Theory-of-Computation       Grammar       Gate-2006
Question 7 Explanation: 
The correct grammar for L = {aibj | i≠j} is
S → AC|CB C → aCb|ϵ A → aA|a B → Bb|b
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 8
 
A
n, E + n and E + n × n
B
n, E + n and E + E × n
C
n, n + n and n + n × n
D
n, E + n and E × n
       Compiler-Design       Grammar       Gate-2005
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.
Question 9
   
A
200
B
180
C
160
D
40
       Compiler-Design       Grammar       Gate-2004
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
Question 10
     
A
{w|Na(w) > 3Nb(w)}
B
{w|Nb(w) > 3Na(w)}
C
{w|Na(w) = 3k, k Î {0, 1, 2, ...}}
D
{w|Nb(w) = 3k, k Î {0, 1, 2, ...}}
       Compiler-Design       Grammar       Gate-2004
Question 10 Explanation: 
S→bS
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
Na(w) > 3Nb(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
Nb(w) > 3Nb(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
Nb(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?  
A
Removing left recursion alone
B
Factoring the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
       Compiler-Design       Grammar       Gate-2003
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.
Question 12
 
A
* has higher precedence than +
B
- has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
       Compiler-Design       Grammar       Gate-2000
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 *.
Question 13
A grammar that is both left and right recursive for a non-terminal, is
A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or unambiguous
D
None of the above
       Theory-of-Computation       Grammar       Gate-1999
Question 13 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 14
 
A
‘⊕’ is left associative while ‘*’ is right associative
B
Both ‘⊕’ and ‘*’ is left associative
C
‘⊕’ is right associative while ‘*’ is left associative
D
None of the above
       Compiler-Design       Grammar       Gate-1997
Question 14 Explanation: 

⊕ is left associative.
* is right associative.
Question 15
Which of the following conversions is not possible (algorithmically)?
A
Regular grammar to context free grammar
B
Non-deterministic FSA to deterministic FSA
C
Non-deterministic PDA to deterministic PDA
D
Non-deterministic Turing machine to deterministic Turing machine
       Theory-of-Computation       Grammar       Gate-1994
Question 15 Explanation: 
NPDA to DPDA conversion is not possible. They have different powers.
Question 16
   
A
Theory Explanation is given below.
       Compiler-Design       Grammar       Gate-2001
There are 16 questions to complete.