Given the language below:
$$L = \left\{w\in (a + b + c)^*: n_a(w) = n_b(w)\text{ or }n_a(w) \ne n_c(w)\right\}$$
How would I prove or disprove that it is either context free.
I know that if it was context free I could create a Grammar for it, or create a push-down automaton.
I know that if it was not context free I could prove it using pumping lemma, however I tried this and realized that it was indeed a context free. I am not sure how to write a grammar or a push-down automaton for this language.
I am wondering if someone could help me out
Thanks in advanced
HINT: Let $$L_1=\left\{w\in(a+b+c)^*:n_a(w)=n_b(w)\right\}$$ and $$L_2=\left\{w\in(a+b+c)^*:n_a(w)\ne n_c(w)\right\}\;;$$ clearly $L=L_1\cup L_2$. If you can construct context-free grammars for $L_1$ and $L_2$ individually, it’s not hard to combine them to produce a CFG for $L$.
Most of the ideas that you need are already used in constructing CFGs for the languages
$$L_1'=\left\{w\in(a+b)^*:n_a(w)=n_b(w)\right\}$$
and
$$L_2'=\left\{w\in(a+b)^*:n_a(w)>n_b(w)\right\}\;;$$
I’ll do that, leaving some of the verification to you along with the task of adapting the ideas to your problem.
Let $L_a$ be the set of $w\in L_1'$ such that no initial segment of $w$ has more $b$’s than $a$’s, and let $L_b$ be the set of $w\in L_1'$ such that no initial segment of $w$ has more $a$’s than $b$’s. These are Dyck words, and it’s well known that $L_a$ and $L_b$ are generated by the grammars
$$A\to AA\mid aAb\mid\epsilon$$
and
$$B\to BB\mid bBa\mid\epsilon\;,$$
respectively. It’s not hard to see that $L_1'=(L_a\cup L_b)^*$, so $L_1'$ is generated by the grammar
$$\begin{align*} &S\to SS\mid A\mid B\\ &A\to AA\mid aAb\mid\epsilon\\ &B\to BB\mid bBa\mid\epsilon\;. \end{align*}$$
$L_2'$ takes a little more work. Suppose that $w=x_1x_2\ldots x_n\in L_2'$, where each $x_k\in\{a,b\}$. Let $c_0=0$, and for $k=1,\ldots,n$ let
$$c_k=\begin{cases} c_{k-1}+1,&\text{if }x_k=a\\ c_{k-1}-1,&\text{if }x_k=b\;; \end{cases}$$
clearly $c_n=n_a(w)-n_b(w)>0$. Let $m=\max\{k:c_k=0\}$; then $x_1\ldots x_m\in L_1'$. Let $L_p$ be the set of $w\in L_2'$ such that $m=0$, i.e., such that $c_k>0$ for $k=1,\ldots,n$, where $n=|w|$; then we’ve just seen that $L_2'=L_1'L_p$, the set of words of the form $uv$ with $u\in L_1'$ and $v\in L_p$. Try to convince yourself that the following grammar generates $L_2'$; $T$ generates $L_1'$, and $P$ generates $L_p$.
$$\begin{align*} &S\to TP\\ &T\to TT\mid A\mid B\\ &A\to AA\mid aAb\mid\epsilon\\ &B\to BB\mid bBa\mid\epsilon\\ &P\to aP\mid aA\mid aAP\mid a \end{align*}$$