4
$\begingroup$

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

S -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> aT

This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

S-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> bT | aTb | bTa

This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'...

I've been trying to think the way where you can input an alphabet (i.e S -> aV | bV) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.

$\endgroup$
9
$\begingroup$

Here are some hints:

  1. Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w) < \#_b(w) \}$. Below we concentrate on $L_a$.

  2. Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.

  3. Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So basically I need to figure out the CFG of (a+b)* where # of a = b, then I use concatenation to put them all together? $\endgroup$ – LarsChung Nov 2 '13 at 7:12
  • $\begingroup$ Well, here is a CFG for $(a+b)^*$: $S \to aS|bS|\epsilon$. Unfortunately, your exercise is more complicated. (Unless by $a,b$ you meant arbitrary expressions $\alpha,\beta$ rather than the symbols $a,b$.) $\endgroup$ – Yuval Filmus Nov 2 '13 at 7:15
  • 1
    $\begingroup$ Unfortunately I am not able answer personal questions. If I remember correctly, MathType can export LaTeX, which you can use here (it is used in my answer). You can answer your question yourself with you suggested solution. $\endgroup$ – Yuval Filmus Nov 4 '13 at 6:33
  • 2
    $\begingroup$ @LarsChung, I suggest you stop guessing and start trying to prove that your grammar works. Your last effort doesn't accept $aabbbbaa$. $\endgroup$ – Yuval Filmus Nov 4 '13 at 16:42
  • 1
    $\begingroup$ I don't know how to $prove$ if my answers work, I can only test cases. Anyway, I've improved it as $S→aSb|bSa|abS|baS|Sab|Sba|SS|ϵ$. Even if I type google how to prove if CFG works, it doesn't give me anything $\endgroup$ – LarsChung Nov 5 '13 at 5:00
4
$\begingroup$

Remember that the following approach is also feasible:

  1. Come up with a pushdown-automaton for the language.
  2. Use the standard construction to get a grammar.

That's not a very insightful process (in terms of learning how to construct grammars) but it works.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yea, I know how to build a PDA with this language, but I have no idea how to convert it to CFG... $\endgroup$ – LarsChung Nov 4 '13 at 5:33
  • 1
    $\begingroup$ @LarsChung Check the proof that PDA and CFG are equally powerful; it usually gives constructions in both directions. $\endgroup$ – Raphael Nov 4 '13 at 10:44
1
$\begingroup$

The unequal number of $a$'s and $b$'s have {equal number of $a$'s and $b$'s} with {{extra $a$'s } or {extra $b$'s}}

Extra $a$'s or extra $b$'s can be

  • at the beginning
  • at the end
  • in between (ANY WHERE) and any number of times

Let $P$ derive strings with extra $a$'s

Let $Q$ derive strings with extra $b$'s

Let $X$ derive equal number of $a$'s and $b$'s

Let $A$ derive only $a$'s

Let $B$ derive only $b$'s

And $S$ derives the final language

\begin{align} &S\rightarrow P\mid Q\\ &P\rightarrow XAX\mid PP\\ &Q\rightarrow XBX\mid QQ\\ &X\rightarrow aXb\mid bXa\mid XX\mid \varepsilon\\ &A\rightarrow aA\mid a\\ &B\rightarrow bB\mid b \end{align}

| cite | improve this answer | |
$\endgroup$
-4
$\begingroup$

$$ \begin{align*} &S → U \mid V \\ &U → TaU \mid TaT \\ &V → TbV \mid TbT \\ &T → aTbT \mid bTaT \mid \epsilon \end{align*} $$

I hope it will predict a context-free grammar for the language consisting of all strings over $\{a,b\}$ containing an unequal number of a's and b's!

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ This is identical to Vigneshwaran's answer from nearly a month ago, except that you use different non-terminals. And your answer is bad for exactly the same reasons theirs is: no explanation at all of why you think it is correct. $\endgroup$ – David Richerby Aug 26 '14 at 16:02
-5
$\begingroup$

I know this is like a very old post, (and way past your homework deadlines), but here's the solution:

$\qquad\begin{align*} L &\to L_a \mid L_b \\ L_a &\to L_=aL_a \mid L_=aL_= \\ L_b &\to L_=bL_b \mid L_=bL_= \\ L_= &\to aL_=bL_= \mid bL_=aL_= \mid \varepsilon \end{align*}$

| cite | improve this answer | |
$\endgroup$
  • 7
    $\begingroup$ How did you get there? Why is it correct? How can the OP or any other reader learn from this for the next task? $\endgroup$ – Raphael Jul 31 '14 at 17:08
-5
$\begingroup$

$$ \begin{align*} &S\to aB \mid bA \\ &A\to b \mid bS \mid aBB \mid \epsilon \\ &B\to a \mid aS \mid bAA \mid \epsilon \end{align*} $$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Where did you get that from? Why is that grammar correct? What are the ideas behind it? We're not looking for one-line answers with no explanation; we're looking for answers that come with explanation, justification, etc. $\endgroup$ – D.W. Jul 31 '17 at 6:10
  • $\begingroup$ FYI - this is wrong, "ab" is a match. $\endgroup$ – CeePlusPlus 4 hours ago

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.