1
$\begingroup$

I need to show that the following language is context free: It contains all words $a^i b^j c^k$ with the condition that there're not exactly as many a's and b's and c's.

I would write it like this: $$\{a^i b^j c^k\; : \;\;!(i=j=k) \;\}$$

Here's what I've come up with:

I split it up into four cases. In three cases two are equal. In the fourth case they're all distinct.

  1. $i=j \neq k: \{a^i b^j c^k : \;i=j \lt k \;\} \cup \{a^i b^j c^k : \;i=j \gt k \;\}$
  2. $i=k \neq j: \{a^i b^j c^k : \;i=k \lt j \;\} \cup \{a^i b^j c^k : \;i=k \gt j \;\}$
  3. $j=k \neq i: \{a^i b^j c^k : \;j=k \lt i \;\} \cup \{a^i b^j c^k : \;j=k \gt i \;\}$
  4. $i \neq j \neq k: \{a^i b^j c^k : i \lt j \lt k \;\} \cup \{a^i b^j c^k : j \lt i \lt k \;\} \cup \{a^i b^j c^k : k \lt i \lt j \;\} \cup \{a^i b^j c^k : k \lt j \lt i \;\}$

I'm not quite sure about the last cause, though.

I do understand how to create a CFG for conditions like $k=i+j$, $(i=j) \lor (j=k)$. But I can't figure out how to create a CFG for these sub-languages.

Any help would be appreciated!

$\endgroup$
8
$\begingroup$

First note that $ \neg(i=j$ and $j=k)$ is $(i \neq j $ or $j \neq k ) $ (Demorgan's Law)

$S \to S_1|S_2 \\ S_1 \to XC \\X \to aA|bB|aXb \\S_2\to AY\\ Y\to bYc|bB|cC\\ A\to aA|\epsilon\\ B\to bB|\epsilon\\ C\to cC|\epsilon$

$\endgroup$
  • $\begingroup$ Thank you so much! I spent hours trying to solve it by going in the wrong direction. $\endgroup$ – ThimoKl Nov 13 '13 at 10:33
0
$\begingroup$

S -> S1 C | S2 C | A S3 | A S4

S1 , #of a's greater than # of b's

S2 , # of a's lesser than # of b's

S3 , # of b's greater than # of c's

S4 , # of b's lesser than # of c's

S -> S1 C | S2 C | A S3 | A S4

S1 -> aA | a S1 b

S2 -> bB | a S2 b

S3 -> bB | b S3 c

S4 -> cC | b S4 c

A -> aA | E

B -> bB | E

C -> cC | E

$\endgroup$
  • $\begingroup$ Hi Naveen! $\color{blue}{\Large\text{Welcome to Math.SE!}}$ Don't worry about it now but you might like to know that we use MathJax here :) $\endgroup$ – Shaun Dec 10 '13 at 11:25

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.