Question

Give a grammar to accept this language: L={ w \in {a,b}* | n _{a}(w) = 2*n _{b}(w) } , (na(w) means the number of a's in w, nb(w) means number of b's in w.) , need an explanation on how to approach this kind of problems

Answer 1

\[L={ w \in {a,b}* | n _{a}(w) = 2*n _{b}(w) }\]

Answer 2

ok, what's you thinking on this? Where did you get stuck specifically?

Answer 3

I dont know how to do it..

Answer 4

What does that language definition mean? Can you explain it to me in English basically :)

Answer 5

w is {a,b}* where the number of a is 2 * number of b

Answer 6

great, so let's come up with 3-4 examples of words that satisfy that definition:
here is one aabbbb -- will it adhere to the rule?

Answer 7

i think so, abb, aaabbbbbb are other examples?

Answer 8

yes, how what about abbabb? does that example fit the language def?

Answer 9

yes? i think since it didnt mention anything about how a's and b's arranged in the language

Answer 10

yep. ok, so let's try to reverse engineer grammar from those examples.
so for every n number of a's you need to have 2n number of b's
I'll help you with the first part:
S=a^n|n>=0 gives you grammar that produces aaaaaaa type of words
how do you add b's to it?

Answer 11

\[S _{1} = b^n | n^2 ?\]

Answer 12

no, n*2 instead of n^2

Answer 13

well you'd want it to be combined with the first, so actually:
S = a^nb^2n|n>=0

But that only gives you coverage for the cases such as aabbb

What about the other case? can you come up with that?

Answer 14

\[S= a^n S b^{2n} | b^{2n} S a^n | \epsilon \]
not sure if this will work

Answer 15

what is | in that equation?

Answer 16

i mean S can be any of the three things after =

Answer 17

Almost there. You might want to simplify it a bit and rewrite with different termination rule (say to terminate on b) but overall it's almost there.

Answer 18

\[S= a^n S _{1} | b^{2n}S _{1} | S _{1} a^n | S _{1} b^{2n} | S _{1}\]

\[S _{1}= a^nS | b^{2n}S | Sa^n | Sb^{2n} | a^{n} | b^{2n} | \epsilon\]

still not sure if this is coorect

Answer 19

Wait, we want the number of `a`s to be twice the number number of `b`s?

Answer 20

I think ultimately we can start of with the empty string, and then we can add onto the left and right of the empty string...
What we add has to be an `a` and two `b`s every time.

Answer 21

I don't think you need to do \(\circ^n\) because we can do things recursively.

Answer 22

\[
\begin{array}{rcl}
S &=& \epsilon\\
&|& aSbb\\
&|& bSab\\
&|& bSba\\
&|& abSb\\
&|& baSb\\
&|& bbSa\\
\end{array}
\]

Answer 23

First cases is empty string

Next three cases are each combination where one letter is on the left, two letters on the right.

Final tree cases are just the reverse of previous three cases. It's interesting to ponder whether they are even necessary. What do you think?

Answer 24

is it better to split them or it will get more complicated ?

Answer 25

Actually there are some rules that I might still be missing here, believe it or not. Such as: \[
| Sabb\\
| Sbab \\
| Sbba \\
| abbS\\
| babS \\
| bbaS \\
\]

Answer 26

Hmm, I think if you create a sub-expression, it could make things easier.

Answer 27

For example, those six rules I just wrote? They are the same as saying: \[
|\quad SS
\]

Answer 28

I really enjoy questions like these.

Answer 29

it is fun, sometimes..

Answer 30

Here is an example of how we could use a sub-expression.
In this case, \(T\) is just any combination of \(a\) and \(b\):\[
\begin{array}{rcl}
T &=& ab\\
&|&ba\\
\\
S &=& \epsilon\\
&|& SS \\
&|& aSbb\\
&|& bbSa\\
&|& bST\\
&|& TSb\\
\end{array}
\]

Answer 31

Here is another idea:\[
\begin{array}{rcl}
R &=& aSb\\
&|&bSa\\
\\
S &=& \epsilon\\
&|& SS \\
&|& bR\\
&|& Rb\\
\end{array}
\]This one is very clean.

Answer 32

In this case \(R\) forms a string where \(n_a(w) = 2 n_b(w) -1\).
We balance it out to \(n_a(w)= 2 n_b(w) \) by adding a \(b\) to \(R\).

Answer 33

Are you getting any ideas now?

Answer 34

Yea thanks i think i am getting the idea, now i just need to practice it

Answer 35

With these problems, you almost always want to avoid things like \(\circ^n\) because it is like using a for loop, when we really want to be using recursion.

Answer 36

Looking at your solution. I could come to the conclusion that \(w=aaaaa\) is a proper solution, which I don't believe is right.

Answer 37

yea i see my mistake now, ill try to avoid using \[0^n\]