| Version 5 |
Version 4 |
| Let $L$ be a regular language (a.k.a. type 3 language). Then there exist |
Let $L$ be a regular language (a.k.a. type 3 language). Then there exist |
| an integer $n$ such that, if the length of a word $W$ is greater |
an integer $n$ such that, if the length of a word $W$ is greater |
| than $n$, then $W = ABC$ where $A,B,C$ are subwords such that |
than $n$, then $W = ABC$ where $A,B,C$ are subwords such that |
| \begin{enumerate} |
\begin{enumerate} |
| \item The length of the subword $B$ is less than $n$. |
\item The length of the subword $B$ is less than $n$. |
| \item The subword $B$ cannot be empty (although one of $A$ or $C$ might |
\item The subword $B$ cannot be empty (although one of $A$ or $C$ might |
| happen to be empty). |
happen to be empty). |
| \item For all integers $k > 0$, it is the case that $AB^kC$ belongs to $L$, |
\item For all integers $k > 0$, it is the case that $AB^kC$ belongs to $L$, |
| where exponentiation denotes repetition of a subword $k$ times. |
where exponentiation denotes repetition of a subword $k$ times. |
| \end{enumerate} |
\end{enumerate} |
|
|
| An important use of this lemma is to show that a language |
An important use of this lemma is to show that a language |
| is not regular. (Remember, just because a language happens to be described |
is not regular. (Remember, just because a language happens to be described |
| in terms of an irregular grammar does not automatically preclude the |
in terms of an irregular grammar does not automatically preclude the |
| possibility of describing the same language also by a |
possibility of describing the same language also by a |
| regular grammar.) The idea is to assume that the language is |
regular grammar.) The idea is to assume that the language is |
| regular, then arrive at a contradiction via this lemma. |
regular, then arrive at a contradiction via this lemma. |
|
|
| An example of such a use of this lemma is afforded by the language |
An example of such a use of this lemma is afforded by the language |
| \[ L = \{0^p 1^q 0^p \mid p,q > 0 \}.\] |
\[ L = \{0^p 1^q 0^p \mid p,q > 0 \}.\] |
| Let $n$ be the number whose existence is guaranteed by the lemma. |
Let $n$ be the number whose existence is guaranteed by the lemma. |
| Now, consider the word $W = 0^{n+1} 1^{n+1} 0^{n+1}$. There must |
Now, consider the word $W = 0^{n+1} 1^{n+1} 0^{n+1}$. There must |
| exist subwords $A,B,C$ such that $W = ABC$ and $B$ must be of length less than $n$. The only possibilities are the following |
exist subwords $A,B,C$ such that $W = ABC$ and $B$ must be of length less than $n$. The only possibilities are the following |
| \begin{enumerate} |
\begin{enumerate} |
| \item $A = 0^u, B = 0^v, C = 0^{n+1-u-v} 1^{n+1} 0^{n+1}$ |
\item $A = 0^u, B = 0^v, C = 0^{n+1-u-v} 1^{n+1} 0^{n+1}$ |
| \item $A = 0^{n+1-u}, B = 0^u 1^v, C = 1^{n+1-v} 0^{n+1}$ |
\item $A = 0^{n+1-u}, B = 0^u 1^v, C = 1^{n+1-v} 0^{n+1}$ |
| \item $A = 0^{n+1} 1^v, B = 1^u, C = 1^{n+1-u-v} 0^{n+1}$ |
\item $A = 0^{n+1} 1^v, B = 1^u, C = 1^{n+1-u-v} 0^{n+1}$ |
| \item $A = 0^{n+1} 1^{n+1-v}, B = 1^v 0^u, C = 0^{n+1-u}$ |
\item $A = 0^{n+1} 1^{n+1-v}, B = 1^v 0^u, C = 0^{n+1-u}$ |
| \item $A = 0^{n+1} 1^{n+1} 0^u, B = 0^v, C = 0^{n+1-u-v}$ |
\item $A = 0^{n+1} 1^{n+1} 0^u, B = 0^v, C = 0^{n+1-u-v}$ |
| \end{enumerate} |
\end{enumerate} |
| In these cases, $AB^2C$ would have the following form: |
In these cases, $AB^2C$ would have the following form: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $AB^2C = 0^{n+1+v} 1^{n+1} 0^{n+1}$ |
\item $AB^2C = 0^{n+1+v} 1^{n+1} 0^{n+1}$ |
| \item $AB^2C = 0^{n+1} 1^v 0^u 1^{n+1} 0^{n+1}$ |
\item $AB^2C = 0^{n+1} 1^v 0^u 1^{n+1} 0^{n+1}$ |
| \item $AB^2C = 0^{n+1} 1^{n+1+u} 0^{n+1}$ |
\item $AB^2C = 0^{n+1} 1^{n+1+u} 0^{n+1}$ |
|
\item $AB^2C = 0^{n+1} 1^{n+1} 0^u 1^v 0^{n+1}$
|
\item $AB^2C = 0^{n+1} 1^{n+1} 0^u, 1^v 0^{n+1}$
|
| \item $AB^2C = 0^{n+1} 1^{n+1} 0^{n+1+u}$ |
\item $AB^2C = 0^{n+1} 1^{n+1} 0^{n+1+u}$ |
| \end{enumerate} |
\end{enumerate} |
|
|
| It is easy to see that, in each of these five cases, $AB^2C \notin L$. |
It is easy to see that, in each of these five cases, $AB^2C \notin L$. |
| Hence $L$ cannot be a regular language. |
Hence $L$ cannot be a regular language. |
|
|
