Peter Linz Edition 4 Exercise 5.1 Question 7.c (Page No. 133)

Question

Find CFG for the following language

L = $\left \{ a^{n}b^{m}: n \neq 2m \right \}$

Comments

$S \rightarrow aaSb\ |\ A\ |\ B$

$A \rightarrow aA\ |\ a$

$B \rightarrow bB​\ |\ b$

---

not accepting $\lambda$

should we add $\lambda$ to S?

---

not able to generate abbb (with all due respect :p)

---

Can it be done like the complement of n=2m?

---

Lambda should not be in L n=0 and m=0 . So n=2m.

You are correct in your second comment. Need to think more.

---

gauravkc we can try, i don't know

new to the topic

---

ohh yeah no need to accept $\lambda$

---

https://www.google.co.in/url?sa=t&source=web&rct=j&url=http://web.cs.ucdavis.edu/~rogaway/classes/494/00/ps4-solns.pdf&ved=2ahUKEwj5vIyTuvvZAhXEto8KHebIAr0QFjAAegQIBxAB&usg=AOvVaw3nqnblvSRjhKfvhKK18z15

---

is that correct?

---

Not sure. I am not able to generate abbb from it (with all due respect :p)

---

haha

---

look at this https://math.stackexchange.com/questions/294518/how-to-construct-a-grammar-g-such-that-lg-anbmn-neq-2m-m-n-ge-0

---

@Utkarsh, Please check for n >2m part

S ---> aS | aaaAb | a

A----> aaAb | aA | epsilon

---

https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxtaXR5cjJzZWNhfGd4OjVhOWZmN2I3YWU0ZGI2OGM

same grammar in solution manual too

---

ankitgupta.1729 looks fine :D

---

It took me more than half an hour to construct these 2 lines..but I dont know u already have the answer :D

---

no that answer in manual is wrong that comment was not for you

---

yours is correct i think

---

ok bro :)

---

similarly for n< 2m?

$S\rightarrow Sb\: |\: aAbbb\: |\:b$
$A\rightarrow aAbb|bA|\epsilon$

---

@Utkarsh , I did not try.. but ur grammar is not accepting ab , a² b² , a³b²...

---

oh yeah

Answer 1

Here ,  L = {aⁿb^m : n ≠ 2m , n ≥ 0 , m ≥ 0}

Now , To write grammar , first we analyze the language and based on this , we will write the grammar... 

Here ,  We have 2 parts in the language :-

1) n > 2m

if m = 0  then accepted strings will be a,a²,a³,a⁴ ...

if m = 1  then accepted strings will be a³b , a⁴b , a⁵b,...

if m  = 2 then accepted strings will be a⁵b² , a⁶b² , a⁷b² , ...

if m = 3 then accepted strings will be a⁷b³ , a⁸b³ , ..

if m =4 then accepted strings will be a⁹b⁴ , a¹⁰b⁴ ,...

Now ,for strings  a,a²,a³,a⁴ , We can write grammar as S ---> aS | a

Now observe 1st string of m=1,2,3,4,.. Similarly 2nd string of m=1,2,3,4...Similarly for 3rd,4th...strings...There is a pattern , a is incrementing 2 times and b is incrementing 1 time every time...Since pattern is starting with aaab.. So , after analyzing the pattern , we can write grammar for this as S ---> aaaAb ;   A---->aaAb | aA

So ,overall grammar for 1st part wil be :-

S ---> aS | aaaAb | a

A ----> aaAb | aA | ɛ

Now ,2nd part of the language wil be  :-

2) n < 2m

For this part ,

n=0 , strings will be b,bb,bbb,.....So, Grammar will be S --> bX  ; X ---> bX | ɛ

now , m = 1 , accepted string is ab (Total 1 string)

m= 2 ,   accepted strings are ab² , a²b² ,a³ b²  (Total 3 strings)

m= 3 , accepted strings are ab³ , a²b³ , a³ b³ , a⁴ b³ ,a⁵b³  (Total 5 strings)

m = 4 ,  accepted strings are ab⁴ , a²b⁴  , a³ b⁴ , a⁴b⁴ , a⁵b⁴ , a⁶ b⁴ , a⁷b⁴ (Total 7 strings)

Now , again there is a pattern ..So, grammar for this , S ---> aBb ;   B ---> Bb | aBb | ɛ

So, Now , After combining both parts , Grammar will be :-

S ----> S₁ | S₂

S₁ ---> aS₁ | aaaAb | a

A ----> aaAb | aA | ɛ

S₂ ---> bX | aBb

X  ---> bX | ɛ

B ----> Bb | aBb | ɛ

Comments

from S2 i'm able to generate bab

---

@Utkarsh ,please check..if there is anything  wrong then please tell me..

---

thanks a lot. It was very tough :o