Redirected
7,185 views
25 votes
25 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$

4 Answers

Best answer
28 votes
28 votes

$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^{m}b^{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 \ldots$ 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 \ldots $ so on ] 

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


Case II [l<m]:

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

$S \rightarrow CB$ one step

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

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

Total steps $= 1 +l+1+m-l = m +2$

So $L =a^lb^m ;l \neq m$ will take $\text{max}(l,m)+2$ steps

Correct Answer: A.

edited by
24 votes
24 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}$


$w=aaaab$

$ 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.

11 votes
11 votes

Q 85

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

Productions used in this sequence:

S-->CB

C-->aCb

C-->aCb

C-->ε

B-->b

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

So, correct answer is option A

0 votes
0 votes

S->AC|CB

Here A dervies the language a+ (i.e a,aa,aaa,.....)

///ly B derives b+ (i.e b,bb,bbb,.....)

C derives a^n b^n   

C Ranges from (Epsilon,ab,aabb,aaabbb,....)

Now there are 2 cases

1)l>m

2)l<m

case-1) l>m  (we should generate a^l b^m and l>m)

 

To generate this you can derive m no of a,b's using C

Therefore we now gets a^m b^m

and given l>m for this case least no of steps to have this is 1 step i.e derive A-->a(So that least value for l which is greater than m is l+1)

 

Therfore S-->AC derivation takes 1 step

And now to derive m a's and b's we need m+1 steps (considering epsilon at the lowest level)

For no of a's to be greater than b's we should have one more derivation i.e A-->a  (1step)

Total no of steps are (m+1)+1+1

Now least value of  l = (m+1) for l>m

therfore minimum no of steps required are l+2

 

case-2)

 

similarly derive s-->CB which takes 1 step

now derive l no of a's and b's (which takes l+1 steps)

and to have m>l we derive one more b i.eB-->b

Therefore (l+1)+1+1

least value for m to be greater than l is l+1

i.e m=l+1

thefore m+2 steps 

Now it depends on max(l,m) as you can see if l>m  then (l+2) steps are required

Else (m+2) steps..

Option A) is correct 

edited by
Answer:

Related questions

33 votes
33 votes
4 answers
2