Consider the grammar
with P given by
Then
so we can write
The string aabb is a sentence in the language generated by G, while aaSbb is a
sentential form.
A grammar G completely defines L (G), but it may not be easy to get a very
explicit description of the language from the grammar. Here, however, the
answer is fairly clear. It is not hard to conjecture that
and it is easy to prove it. If we notice that the rule S → aSb is recursive, a proof
by induction readily suggests itself. We first show that all sentential forms must
have the form
Suppose that (1.7) holds for all sentential forms w i of length 2i + 1 or less. To get
another sentential form (which is not a sentence), we can only apply the
production S → aSb. This gets us
so that every sentential form of length 2i + 3 is also of the form (1.7). Since (1.7)
is obviously true for i = 1, it holds by induction for all i. Finally, to get a
sentence, we must apply the production S → λ, and we see that
with P given by
Then
so we can write
The string aabb is a sentence in the language generated by G, while aaSbb is a
sentential form.
A grammar G completely defines L (G), but it may not be easy to get a very
explicit description of the language from the grammar. Here, however, the
answer is fairly clear. It is not hard to conjecture that
and it is easy to prove it. If we notice that the rule S → aSb is recursive, a proof
by induction readily suggests itself. We first show that all sentential forms must
have the form
Suppose that (1.7) holds for all sentential forms w i of length 2i + 1 or less. To get
another sentential form (which is not a sentence), we can only apply the
production S → aSb. This gets us
so that every sentential form of length 2i + 3 is also of the form (1.7). Since (1.7)
is obviously true for i = 1, it holds by induction for all i. Finally, to get a
sentence, we must apply the production S → λ, and we see that