Peter Linz Exercise 5.1

Question

Find context free grammars for the following languages (with n>=0, m>=0, k>=0)

(a) L={aⁿb^mc^k : n=m or m<=k}

(b) L={ aⁿb^mc^k : n=m or m≠k}

(c) L={aⁿb^mc^k  : k=n+m }

(d) L={ aⁿb^mc^k : n+2m=k}

(e) L={aⁿb^mc^k : k=|n-m| } 

(f) L={ w ∈ {a,b,c}^* : n_a(w)+n_b(w)≠n_c(w) }

(g) L={ aⁿb^mc^k  : k≠n+m }

(h) L= { aⁿb^mc^k : K>=3} 

Comments

f) is similar like g)

I think u got it.

if not ask me again

---

is this correct for (f) ????

S→A | B
A→ AA | aAc | cAa | bAc | cAb | a | b | ϵ

B→ BB | aBc | cBa | bBc | cBb | c| ϵ

 

---

@ayush “  S1 --> aS1c | c | cS1 | A  “

in this instead of CS1 it should be S1c

Answer 1

C

S→aSc | B

B→ bBc | ϵ

d

S→aSc | B

B→ bBcc | ϵ

Answer 2

A - NCFL

B - NCFL

C,D,E,G,H-CFL right ??

Comments

(H) is regular language.

Answer 3

(a)

 

S→A | B

A→ CD

C→ aCb | ϵ

D→Dc | ϵ

B→EF

E→aE | ϵ

F→bFc | G
G→Gc | ϵ 

 

 

Answer 4

(b)

S→A | B
A→ CD

C→ aCb | ϵ

D→Dc | ϵ

B→EF

E→aE | ϵ

F→bFc | G |  H

G→Gc | ϵ

H→bH | ϵ