GATE 2005
March 12, 2025GATE 2006
March 12, 2025GATE 2006
| Question 85 |
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?
| max(l,m)+2 | |
| l+m+2 | |
| l+m+3 | |
| max(l, m)+3 |
Question 85 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
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
Correct Answer: A
Question 85 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
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
Subscribe
Login
0 Comments