Need to create a context-free language

53 Views Asked by At

I need to create a context-free language for the following language.

$$L = \{w\in\Sigma^\ast \mid w = a^k b^m c^n \text{ where } k,m,n\in\mathbb N \text{ and } k<m \vee k>n\}$$

Here ^ is the empty string

S=  aAb | AbB | bBC | aTbBbc 
A = aA | aAb | ^
B = BbB | ^
C = cC | ^
T = aTb | ^

I got the following setup which accepts the words a,b,bc,bb,bbc,aabc,abbcccc, etc.., the only one missing is words in the form of "aaaaabccc", or where $k > m$ and $m > n$.

The problem is that I'm bound to 5 variables and 14 rules, but I can't figure out how to add a rule to detect the missing string into my current implementation.

1

There are 1 best solutions below

1
On

Perhaps this works -

S = PC | Q
C = cC | ^
P = Pb | aPb | b
B = bB | ^
Q = aQc | aQ | aB

Thanks