Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 1 down vote accepted

HINTS:

(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|improve this answer

Your Answer

 
discard

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.