Grammar

Question 1

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-ComputationGrammarGATE 2006
Question 1 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 2

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-ComputationGrammarGATE 2006
Question 2 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 3

Consider the grammar: 

  E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are:

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-DesignGrammarGATE 2005
Question 3 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 4

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T     {E.value = E1.value * T.value}
    |    T     {E.value = T.value}
T → T1 & F     {T.value = T1.value + F.value}
    |    F     {T.value = F.value}
F → num        {F.value = num.value}

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

A
200
B
180
C
160
D
40
Compiler-DesignGrammarGATE 2004
Question 4 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
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access