# Context Free Grammars - nobody was able to answer

• May 6th 2010, 11:45 PM
hekticity
Context Free Grammars - nobody was able to answer
Hey people,

Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

Find context-free grammars for the following languages:

(a)

L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

(b)

L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

• May 7th 2010, 01:52 AM
kompik
Quote:

Originally Posted by hekticity
Hey people,

Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

Find context-free grammars for the following languages:

(a)

L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

(b)

L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

If I understand you correctly, the first language contains the words with the same number of occurrences of a's and e's; in b these numbers are different.

I would try something like this (I guess you can try to simplify it):
S->aE|Ea|eA|Ae| $\varepsilon$
E->eS|Se|EaE|aEE|EEa
A->aS|Sa|AeA|eAA|AAe

The basic idea is that whatever word you can derive from A, it will have one more a then e. The hard part is to prove that this can generate all words. (That's why I suggested that you should first think about simplifying this grammar.)

IMHO you can solve the part b in a similar fashion.
First you decide that you have say 4 more e's than a's.
You start like S => S1, where S1 is a symbol from which you can generate only words with more e's then a's. You do several steps to obtain something like S2eS2eS2eS2eS2 and then apply the rules for S2. You have to make the rules for S2 in a such way, that S2 generates only words with the same number of both symbols. (Again, you can try to simplify this or to make a completely different grammar, but the basic idea I gave you above should help you.)
• May 7th 2010, 03:46 AM
undefined
Quote:

Originally Posted by hekticity
Hey people,

Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

Find context-free grammars for the following languages:

(a)

L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

(b)

L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)

For part (a) I think this would also work

S -> eaS | eSa | Sea | aeS | aSe | Sae | $\varepsilon$

I have limited experience with these so someone please correct me if I'm wrong.

Edit: By the way, part (b) is Example 6 in this article on Wikipedia.
• May 7th 2010, 03:54 AM
kompik
Quote:

Originally Posted by undefined
For part (a) I think this would also work

S -> eaS | eSa | Sea | aeS | aSe | Sae | $\varepsilon$

I have limited experience with these so someone please correct me if I'm wrong.

Edit: By the way, part (b) is Example 6 in this article on Wikipedia.

I do not see how you get the word eeaaaaee. But I might have overlooked something. (I am not an expert in this area, either. I had some basic course on formal languages and automata - it was quite a long time ago.)
• May 7th 2010, 03:57 AM
undefined
Quote:

Originally Posted by kompik
I do not see how you get the word eeaaaaee. But I might have overlooked something. (I am not an expert in this area, either. I had some basic course on formal languages and automata - it was quite a long time ago.)

You're probably right. I'm wondering what language my grammar describes, then.

Edit: You're definitely right. It's pretty easy to see that the only non-empty strings possible either begin or end with ea or ae, or begin with an e and end with an a, or begin with an a and end with an e.
• May 7th 2010, 04:05 AM
undefined
Actually, Example 6 in the previously referenced Wikipedia article says that "...the nonterminal T can generate all strings with the same number of a's as b's...."

Do I understand correctly that

S -> aSbS | bSaS | $\varepsilon$

is a solution to part (a)?
• May 7th 2010, 05:29 AM
kompik
Quote:

Originally Posted by undefined
Actually, Example 6 in the previously referenced Wikipedia article says that "...the nonterminal T can generate all strings with the same number of a's as b's...."

Do I understand correctly that

S -> aSbS | bSaS | $\varepsilon$

is a solution to part (a)?

Yes, you're right. And this solution is much better than mine, since it is very easy to show that this grammar generates L.

Obviously, by induction you can show that each sentential form (anything you can derive from S) has as many a's as b's.

By induction on n we show next, that if a word w consists of n a's and n b's, then there is a derivation for it.

n=0,1 is easy.

Inductive step: Suppose that n_a(w)=n_b(w)=n.
Let $w=a_1a_2\dots a_{2n}$
W.l.o.g., let w starts with a letter a, i.e., $a_1=a$.
Let k be smallest number such that the count of a's and b's in $a_1a_2\dots a_k$ is the same. (Since this is true for $k=2n$, such k exists.)
Clearly, $a_k=b$. (Otherwise k cannot be minimal.)

So, w can be rewritten in the form
$w=aw_1bw_2$,
where both $w_1$ and $w_2$ belong to L(G), i.e., they can be derived from S (by inductive hypothesis).

A derivation for goes like: $S\Rightarrow aSbS\Rightarrow^* aw_1bS \Rightarrow^* aw_1bw_2$.
• May 7th 2010, 07:25 AM
hekticity
Thankyou very much both of you..

so what is the answer to (A) (what exactly is the answer??)? Undefined's response or kompik?

Any ideas on (B)?
• May 7th 2010, 10:15 AM
kompik
Quote:

Originally Posted by hekticity
Thankyou very much both of you..

so what is the answer to (A) (what exactly is the answer??)? Undefined's response or kompik?

Any ideas on (B)?

If you read this thread carefully, you must notice that you were given answers to both parts and for (A) we have also sketched a proof that the answer is correct.