|
|
|
Viewing Version
5
of
'Kuroda normal form'
|
[ view 'Kuroda normal form'
|
back to history
]
| Title of object: |
Kuroda normal form |
| Canonical Name: |
KurodaNormalForm |
| Type: |
Definition |
| Created on: |
2009-07-02 23:32:49 |
| Modified on: |
2009-07-08 20:18:53 |
| Classification: |
msc:68Q45, msc:68Q42 |
| Defines: |
one-sided normal form |
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
\usepackage{multicol}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} |
Content:
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:
\begin{enumerate}
\item $A\to a$,
\item $A\to BC$,
\item $AB\to CD$.
\end{enumerate}
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 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:
\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
\begin{multicols}{2}{
\begin{enumerate}
\item $AB\to AX$ \\ [-3ex]
\item $AX\to YX$ \\ [-3ex]
\item $YX\to YD$ \\ [-3ex]
\item $YD\to CD$ \\ [-3ex]
\end{enumerate}}
\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:
\begin{enumerate}
\item $A\to a$,
\item $A\to BC$,
\item $AB\to AC$,
\item $AB\to CB$.
\end{enumerate}
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}
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.
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{enumerate}
\item $A\to a$,
\item $A\to BC$,
\item $AB\to AC$,
\item $A\to \lambda$.
\end{enumerate}
\end{thm}
\begin{thebibliography}{9}
\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).
\end{thebibliography} |
|
|
|
|
|
