The language
is context-free.
To show this, we need to produce a context-free grammar for the language.
The case of n = m is solved in Example 1.11 and we can build on that solution.
Take the case n > m. We first generate a string with an equal number of a's and
b's, then add extra a's on the left. This is done with
We can use similar reasoning for the case n < m, and we get the answer
The resulting grammar is context-free, hence L is a context-free language.
However, the grammar is not linear.
The particular form of the grammar given here was chosen for the purpose of
illustration; there are many other equivalent context-free grammars. In fact, there
are some simple linear ones for this language. In Exercise 26 at the end of this
section you are asked to find one of them.
Example 5.4
Consider the grammar with productions
This is another grammar that is context-free, but not linear. Some strings in L(G)
are abaabb, aababb, and ababab. It is not difficult to conjecture and prove that
is context-free.
To show this, we need to produce a context-free grammar for the language.
The case of n = m is solved in Example 1.11 and we can build on that solution.
Take the case n > m. We first generate a string with an equal number of a's and
b's, then add extra a's on the left. This is done with
We can use similar reasoning for the case n < m, and we get the answer
The resulting grammar is context-free, hence L is a context-free language.
However, the grammar is not linear.
The particular form of the grammar given here was chosen for the purpose of
illustration; there are many other equivalent context-free grammars. In fact, there
are some simple linear ones for this language. In Exercise 26 at the end of this
section you are asked to find one of them.
Example 5.4
Consider the grammar with productions
This is another grammar that is context-free, but not linear. Some strings in L(G)
are abaabb, aababb, and ababab. It is not difficult to conjecture and prove that