I'm trying to find a CFG for the language:
$$L = \{a^nb^mc^o: n = m \text{ or } m \neq o\}$$
The or is tripping me up in the language. So far I have something like:
$$\begin{align}S &\to A | B \\ A &\to aAb | \epsilon \\ B &\to aB | C | E \\ C &\to bCc | bD \\ D &\to bD | \epsilon \\ E &\to bEc | Fc \\ F &\to Fc | \epsilon \end{align}$$
In order of lines above:
- split problem into two subproblems
- add equal a and b or end (follows $n = m$)
- add any number of a
- add equal b and c or add b
- then add b or end (follows $m > o$)
- add equal b and c or add c
- then add c or end (follows $m < o$)
My thought process is if $m > o$ or $m < o$, then $m \neq o$, thus both conditions are satisfied, but this is incorrect for the first part of the or conditional: $n = m$. Note I can't have strings like $abcc$ which satisfies both conditions because a $c$ cannot be added if $n = m$ in line $A \to aAb | \epsilon$.
A more declarative language for the CFG I have is:
$$L = \{a^nb^mc^o : (n = m \text{ when } o = 0) \text{ or } m \neq o\}$$
Which is not the language the question asks me of. I just can't wrap my head around it.