Construct Greibach Normal Form for the intersection of \(0^*1^*0^*1^*\) with \(L\), where \(L\) is the language of all non-empty palindromes given in Example 7.29.
First observe that a non-empty palindrome matching \(0^*1^*0^*1^*\) must match one of these four expressions,
- \(0^+1^+0^+\) and \(1^+0^+1^+\),
- \(1^+\) and \(0^+\).
Now we construct a grammar \((\left\{ S,T,U,V,W\right\}, \left\{ 0,1\right\}, P, S)\) with the rules given by \[\begin{align*} S&\to 0T0 | 1U1 | 0V | 0 | 1W | 1 \\ T&\to 0T0 | 1W \\ U&\to 1U1 | 0V \\ V&\to 0V | 0 \\ W&\to 1W | 1 \end{align*}\] and we normalise it by adding two more non-terminals \(\left\{ \overline{0}, \overline{1}\right\}\) and changing the rules to \[\begin{align*} S&\to 0T\overline{0} | 1U\overline{1} | 0V | 0 | 1W | 1 \\ T&\to 0T\overline{0} | 1W \\ U&\to 1U\overline{1} | 0V \\ V&\to 0V | 0 \\ W&\to 1W | 1 \\ \overline{0}&\to 0 \\ \overline{1}&\to 1 \end{align*}\]