In a book there is an example where it's showed that a grammar G generates a
language L where each word is composed by an equal number of "a" and "b"
(eg. ab, aabb, ...).

So follows a proof where the book says that is easy to see that in each word
of L(G) the number of "a" is equal to the number of "b".

Here it's all ok, but why is it insufficient? Infact, the book continues the
proof using the mathematical induction, but why? 
If we already know that each word of L(G) is equal to the one of L, why is
it necessary continue?

Regards.

Ronnie <no@spam.it> wrote:
> In a book there is an example where it's showed that a grammar G generates a
> language L where each word is composed by an equal number of "a" and "b"
> (eg. ab, aabb, ...).

Which book? It's a bit hard for me to talk about proofs I have not yet
seen.

> So follows a proof where the book says that is easy to see that in
> each word of L(G) the number of "a" is equal to the number of "b".
 
So L(G) is a subset of L since every word generated by G is an element
of L.

> Here it's all ok, but why is it insufficient? 

Imagine a Grammar G'=(V,\Sigma,P,S): V={S}, \Sigma={a,b} and the only
production in P is S->ab.

It is easy to see that the only word generated by G is "ab" that
contains as many a's as b's. So L(G') is a subset of L.

The problem now is: there are many many other words that "my" grammar
does not generate but actually should. So if I could prove that every
word with an equal number of a's and b's can be generated with my
grammar, everything should be fine. But I can't. So L(G') != L.

See the problem?

> Infact, the book continues the proof using the mathematical induction,
> but why?  

I think they are showing that every word containing as many a's as b's
can be generated by this grammar. Hence L is a subset of L(G). So now -
and only now - you get L=L(G), meaning that the grammar generates L and
only L.

> If we already know that each word of L(G) is equal to the
> one of L, why is it necessary continue?

Most likely this has not been shown in the first part of the proof.

  Florian

thanks for your precious help!

Greetings.