| Version 6 |
Version 5 |
| Just like every context-free grammar can be ``normalized'' or ``standardized'' in one of the so-called \PMlinkname{normal forms}{ChomskyNormalForm}, so can a context-sensitive grammar be normalized. The particular normalization discussed in this entry is what is known as the Kuroda normal form. |
Just like every context-free grammar can be ``normalized'' or ``standardized'' in one of the so-called \PMlinkname{normal forms}{ChomskyNormalForm}, so can a context-sensitive grammar be normalized. The particular normalization discussed in this entry is what is known as the Kuroda normal form. |
|
|
| A formal grammar $G=(\Sigma,N,P,\sigma)$ is in \emph{Kuroda normal form} if its productions have one of the following forms: |
A formal grammar $G=(\Sigma,N,P,\sigma)$ is in \emph{Kuroda normal form} if its productions have one of the following forms: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $A\to a$, |
\item $A\to a$, |
| \item $A\to BC$, |
\item $A\to BC$, |
| \item $AB\to CD$. |
\item $AB\to CD$. |
| \end{enumerate} |
\end{enumerate} |
| where $a\in \Sigma-N$ and $A,B,C,D\in N$. |
where $a\in \Sigma-N$ and $A,B,C,D\in N$. |
|
|
| Note: Sometimes the form $A\to B$, where $B\in N$ is added to the list above. However, we may remove a production of this form by replacing all occurrences of $B$ by $A$ in every production of $G$. |
Note: Sometimes the form $A\to B$, where $B\in N$ is added to the list above. However, we may replace a production of this form by replacing all occurrences of $B$ by $A$ in every production of $G$. The usefulness of the Kuroda normal forms is captured in the following result: |
|
|
| The usefulness of the Kuroda normal forms is captured in the following result: |
|
|
|
| \begin{thm} A grammar is length-increasing iff it is equivalent to a grammar in Kuroda normal form. \end{thm} |
\begin{thm} A grammar is length-increasing iff it is equivalent to a grammar in Kuroda normal form. \end{thm} |
|
|
| Note that the third production form $AB\to CD$ may be replaced by the following productions |
Note that the third production form $AB\to CD$ may be replaced by the following productions |
| \begin{multicols}{2}{ |
\begin{multicols}{2}{ |
| \begin{enumerate} |
\begin{enumerate} |
| \item $AB\to AX$ \\ [-3ex] |
\item $AB\to AX$ \\ [-3ex] |
| \item $AX\to YX$ \\ [-3ex] |
\item $AX\to YX$ \\ [-3ex] |
|
|
| \item $YX\to YD$ \\ [-3ex] |
\item $YX\to YD$ \\ [-3ex] |
| \item $YD\to CD$ \\ [-3ex] |
\item $YD\to CD$ \\ [-3ex] |
| \end{enumerate}} |
\end{enumerate}} |
| \end{multicols} |
\end{multicols} |
| where $X,Y$ are new non-terminals introduced to $G$. Note also that, among the new forms, 1 and 3 are right context-sensitive, while 2 and 4 are left context-sensitive. Thus, a grammar in Kuroda normal form is equivalent to a grammar with productions having one of the following forms: |
where $X,Y$ are new non-terminals introduced to $G$. Note also that, among the new forms, 1 and 3 are right context-sensitive, while 2 and 4 are left context-sensitive. Thus, a grammar in Kuroda normal form is equivalent to a grammar with productions having one of the following forms: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $A\to a$, |
\item $A\to a$, |
| \item $A\to BC$, |
\item $A\to BC$, |
| \item $AB\to AC$, |
\item $AB\to AC$, |
| \item $AB\to CB$. |
\item $AB\to CB$. |
| \end{enumerate} |
\end{enumerate} |
| It can be shown that |
It can be shown that |
|
|
| \begin{thm} A grammar in Kuroda normal form if it is equivalent to a grammar whose productions are in one of forms $1,2$, or $3$. \end{thm} |
\begin{thm} A grammar in Kuroda normal form if it is equivalent to a grammar whose productions are in one of forms $1,2$, or $3$. \end{thm} |
|
By symmetry, a grammar in Kuroda normal form is equivalent to a grammar whose productions are in one of forms $1,2$, or $4$. A grammar whose productions are in one of forms $1,2$, or $3$ is said to be in \emph{one-sided normal form}.
|
By symmetry, a grammar in Kuroda normal form is equivalent to a grammar whose productions are in one of forms $1,2$, or $3$. A grammar whose productions are in one of forms $1,2$, or $3$ is said to be in \emph{one-sided normal form}.
|
|
|
| As a corollary, every $\lambda$-free context-sensitive language (not containing the empty word $\lambda$) can be generated by a grammar in one-sided normal form. |
As a corollary, every $\lambda$-free context-sensitive language (not containing the empty word $\lambda$) can be generated by a grammar in one-sided normal form. |
|
|
| What if we throw in production of the form $A\to \lambda$ in the above list? Then certainly every context-sensitive language has a grammar in this ``extended'' normal form. In fact, we have |
What if we throw in production of the form $A\to \lambda$ in the above list? Then certainly every context-sensitive language has a grammar in this ``extended'' normal form. In fact, we have |
| \begin{thm} Every type-0 language can be generated by a grammar whose productions are in one of the following forms: |
\begin{thm} Every type-0 language can be generated by a grammar whose productions are in one of the following forms: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $A\to a$, |
\item $A\to a$, |
| \item $A\to BC$, |
\item $A\to BC$, |
| \item $AB\to AC$, |
\item $AB\to AC$, |
| \item $A\to \lambda$. |
\item $A\to \lambda$. |
| \end{enumerate} |
\end{enumerate} |
| \end{thm} |
\end{thm} |
|
|
| \begin{thebibliography}{9} |
\begin{thebibliography}{9} |
| \bibitem{AS} G. E. R\'{e}v\'{e}sz, {\em Introduction to Formal Languages}, Dover Publications (1991). |
\bibitem{AS} G. E. R\'{e}v\'{e}sz, {\em Introduction to Formal Languages}, Dover Publications (1991). |
| \bibitem{ms} A. Mateescu, A. Salomaa, {\em Chapter 4 - Aspects of Classical Language Theory, Handbook of Formal Languages: Volume 1. Word, Language, Grammar}, Springer, (1997). |
\bibitem{ms} A. Mateescu, A. Salomaa, {\em Chapter 4 - Aspects of Classical Language Theory, Handbook of Formal Languages: Volume 1. Word, Language, Grammar}, Springer, (1997). |
| \end{thebibliography} |
\end{thebibliography} |
