The Gateway to Computer Science Excellence


+13 votes

The grammar

  • $S\rightarrow AC\mid CB$
  • $C\rightarrow aCb\mid \epsilon$
  • $A\rightarrow aA\mid a$
  • $B\rightarrow Bb\mid b$

generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$

  1. $\max (l,m) + 2$
  2. $l + m + 2$
  3. $l + m + 3$
  4. $\max (l,m) + 3$
in Compiler Design by Veteran | 1.5k views

@jothee answer and quetion already here.

5 Answers

+10 votes
Best answer

$L =a^lb^m$ $l$ $\neq m$ means either $l > m$ or $l < m$ 

Case I[l > m]

if $l >m$ ,$a^lb^m$ can be written as $\mathbf{a^{l-m}a^mb^m}$  [$l-m$ cannot be $0$ as $l$ should be $> m$ ]

S$\rightarrow$ AC , one step 

$a^{l-m}$ use $l-m$ steps using productions of A 

[as $l-m = 1$ , one step A $\rightarrow$ a

$l-m =2$ , two steps A $\rightarrow$aA $\rightarrow$aa 

$l-m = 3$ , three steps , A$\rightarrow$aA$\rightarrow$aaA$\rightarrow$aaa.. so on]

$a^mb^m$ will be generate in $m + 1$ steps using production C  

[ as $m = 0$ one step C $\rightarrow$ $\epsilon$

$m= 1$ , two steps C $\rightarrow$ aCb $\rightarrow$ ab 

$m= 2$, three steps C $\rightarrow$ aCb $\rightarrow$aaCbb$\rightarrow$ aabb.. so on ] 

so if $l>m$ total steps $= 1+l-m +m+1 = l +2$

Case II [l<m]

simillar if $l< m$ , $a^lb^m$ can be written as $\mathbf{a^lb^lb^{m-l}}$ [$m-l$ cannot be $0$ as $m$ should be $> l$ ]

S$\rightarrow$ CB one step

$a^lb^l$ will be derives using $l+1$ steps 

$b^{m-l}$ will be derived using $m- l$ steps 

total $= 1 +l+1+m-l = m +2 $

so $L =a^lb^m$ $l \neq m$ will take $max(l,m)+2$ steps

Correct Answer: $A$

by Veteran
edited by
absolutely Brilliant👍
+19 votes

Option A is correct. We can try some strings:

$w = {a^l}{b^m},l\neq m \Rightarrow aabbb\\ S \rightarrow \underset{1}{CB}\rightarrow\underset{2}{ aCbB}\rightarrow \underset{3}{ aaCbbB}\rightarrow \underset{4}{aaCbbB}\rightarrow \underset{5}{aabbb}$

$ w= aaaabb\\ S\rightarrow \underset{1}{AC}\rightarrow \underset{2}{AaCb}\rightarrow \underset{3}{AaaCbb}\rightarrow \underset{4}{Aaa\epsilon bb}\rightarrow \underset{5}{aAaabb}\rightarrow \underset{6}{aaaabb}$


$ S\rightarrow \underset{1}{AC}\rightarrow \underset{2}{AaCb}\rightarrow \underset{3}{Aa\varepsilon b}\rightarrow\underset{4} {aAab}\rightarrow\underset{5} {aaAab}\rightarrow \underset{6}{aaaab}$

In cases $2$ and $3$ reducing number of $b's$ has no affect on the number of productions required.

by Active
while deriving a string can we replace more than one non terminal with a terminal in one step?
More than one terminal or not should not be your concern.Use only 1 production per step.
No, only one Non terminal at each step.
+9 votes

Q 85

Let us take aabbb as an example to check in the options[l=2, m=3]

Productions used in this sequence:






total 5 sequences are used.  Only option A satisfies this.

So, correct answer is option A

by Active
0 votes
Part A
0 votes
option  A

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,811 answers
118,086 users