1.5k views

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$
| 1.5k views
0

https://gateoverflow.in/1856/gate2006_84-85

0

$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
+1
absolutely Brilliant👍

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.

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

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

by Active