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.
Perhaps this works -
Thanks