396 views
0 votes
0 votes
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$).
(a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}.
(b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}.
(c) $L =$ {$a^nb^mc^k : k = n + m$}.
(d) $L =$ {$a^nb^mc^k : n + 2m = k$}.
(e) $L =$ {$a^nb^mc^k : k = |n − m|$}.
(f) $L =$ {$w ∈$ {$a, b, c$}$^* : n_a (w) + n_b (w) ≠ n_c (w)$}.
(g) $L =$ {$a^nb^mc^k, k ≠ n + m$}.
(h) $L =$ {$a^nb^mc^k : k ≥ 3$}.

4 Answers

0 votes
0 votes

(a)

 

S→A | B

A→ CD

C→ aCb | ϵ

D→Dc | ϵ

B→EF

E→aE | ϵ

F→bFc | G
G→Gc | ϵ 

0 votes
0 votes

b)

S→A | B
A→ CD

C→ aCb | ϵ

D→Dc | ϵ

B→EF

E→aE | ϵ

F→bFc | G |  H

G→Gc | ϵ

H→bH | ϵ 

0 votes
0 votes

f)

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

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

Related questions

1 votes
1 votes
1 answer
1