Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Find context free grammar for a given language and prove its correctness:

a) $\left\{ a^ib^ja^k : i\neq j \ \vee \ j\neq k \right\}$

b) $\left\{ w\in \left\{a,b\right\}^* : \#_a(w)=2 \cdot \#_b(w) \right\}$

c) set of all words $w\in \left\{ a,b \right\}^*$ that have even length and numbers of occurrences of $b$ on even and odd positions are equal.

For a) and c) I have no idea. For b) I think I found it: $$S\rightarrow SaSaSbS \ | \ SaSbSaS \ | \ SbSaSaS \ | \ \varepsilon$$ Seems correct, but don't know how to prove that every word that has twice many $a$'s than $b$'s can be produced by this grammar. Can anybody help?

share|cite|improve this question
up vote 1 down vote accepted


(a) This is the union of the languages $\left\{a^ib^ja^k:i<j\right\}$, $\left\{a^ib^ja^k:i>j\right\}$, $\left\{a^ib^ja^k:j<k\right\}$, and $\left\{a^ib^ja^k:j>k\right\}$, and it’s not too hard to write context-free grammars for these languages.

(b) Finding a proof that your grammar generates the language $L=\{w\in\{a,b\}^*:|w|_a=|w|_b\}$ seems a bit difficult, but I can do it for a somewhat different grammar. Say that $w\in L$ is irreducible if it is non-empty and not of the form $uv$ for any non-empty $u,v\in L$. Prove that if $w$ is irreducible, then there is a $u\in L$ such that $w\in\{aaub,abua,buaa\}$. Then consider the grammar with these productions:

$$\begin{align*} &S\to TS\mid\varepsilon\\ &T\to aaSb\mid abSa\mid bSaa \end{align*}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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