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




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$$


$$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*}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.