Kuroda normal form

The Kuroda normal form is a term used in theoretical computer science that is of interest in connection with context-sensitive languages . It is named after the linguist Sige-Yuki Kuroda and describes a normal form of monotonous grammars , i.e. a subset of monotonous grammars that does not lose any expressiveness compared to the set of all monotonous grammars. The importance of the Kuroda normal form lies in the very simple structure of the productions . Because monotonous grammars and context-sensitive grammars are sometimes not differentiated, the Kuroda normal form is also referred to as the normal form of context-sensitive grammars.

The Kuroda normal form is a generalization of the Chomsky normal form , which is a normal form for context-free grammars.

definition

A formal grammar is in Kuroda normal form (short KNF , not to be confused with "KNF" - conjunctive normal form ) if all productions have the following form:

• ${\displaystyle A\rightarrow a}$
• ${\displaystyle A\rightarrow B}$
• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle AB\rightarrow CD}$

where , , and variables and a terminal symbol. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle a}$

If the second and fourth rule forms do not occur, the grammar is in Chomsky normal form .

properties

• Every grammar in Kuroda normal form is a monotonous grammar .
• At any monotonic grammar with a monotonic grammar exists in Kuroda normal form, generating the same language, that is, . is then also called a Kuroda normal form of the monotonous grammar . ${\displaystyle G_{1}}$ ${\displaystyle \varepsilon \notin L(G_{1})}$ ${\displaystyle G_{2}}$ ${\displaystyle L(G_{1})=L(G_{2})}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{1}}$

Conversion of a grammar into Kuroda normal form

Be a monotonous grammar with . A Kuroda normal form of can be constructed like this: ${\displaystyle G_{1}=(V_{1},\Sigma ,P_{1},S)}$ ${\displaystyle \epsilon \notin L(G_{1})}$ ${\displaystyle G_{2}=(V_{2},\Sigma ,P_{2},S)}$ ${\displaystyle G_{1}}$

• All terminal symbols that appear in are replaced by a new variable , and the new productions are introduced for each terminal symbol . ${\displaystyle P_{1}}$ ${\displaystyle a}$ ${\displaystyle A_{a}}$ ${\displaystyle a}$ ${\displaystyle A_{a}\rightarrow a}$
• Each production of the form is replaced by the following new productions: , for all and . There are new variables. ${\displaystyle A\rightarrow A_{1}A_{2}\dotso A_{k}}$ ${\displaystyle A\rightarrow A_{1}B_{1}}$ ${\displaystyle B_{i}\rightarrow A_{i+1}B_{i+1}}$ ${\displaystyle i\in \{1,\dotsc ,k-3\}}$ ${\displaystyle B_{k-2}\rightarrow A_{k-1}A_{k}}$ ${\displaystyle B_{1},\dotsc ,B_{k-2}}$
• Each production of the mold , with is replaced by the following new productions: for all : for all : and . There are new variables. ${\displaystyle A_{1}A_{2}\dotso A_{l}\rightarrow B_{1}B_{2}\dotso B_{k}}$ ${\displaystyle 2\leq l\leq k}$ ${\displaystyle 3\leq k}$ ${\displaystyle A_{1}A_{2}\rightarrow B_{1}C_{1}}$ ${\displaystyle i\in \{1,\dotsc ,l-2\}}$ ${\displaystyle C_{i}A_{i+2}\rightarrow B_{i+1}C_{i+1}}$ ${\displaystyle i\in \{l-1,\dotsc ,k-3\}}$ ${\displaystyle C_{i}\rightarrow B_{i+1}C_{i+1}}$ ${\displaystyle C_{k-2}\rightarrow B_{k-1}B_{k}}$ ${\displaystyle C_{1},\dotsc ,C_{k-2}}$

The grammar thus generated is in Kuroda normal form and produces the same language as the grammar before.

Révész normal form

Every monotonous grammar in Kuroda normal form can be converted into a context-sensitive grammar in Révész normal form. For this purpose, two new non-terminals are introduced for each production rule of the form and the rule is replaced by four rules: ${\displaystyle G_{1}=(V_{1},\Sigma ,P_{1},S)}$ ${\displaystyle G_{2}=(V_{2},\Sigma ,P_{2},S)}$ ${\displaystyle AB\rightarrow CD\in P_{1}}$ ${\displaystyle W,Z\in V_{2}}$

• ${\displaystyle AB\rightarrow AZ}$
• ${\displaystyle AZ\rightarrow WZ}$
• ${\displaystyle WZ\rightarrow WD}$
• ${\displaystyle WD\rightarrow CD}$

A context-sensitive grammar is in Révész normal form when all productions have the following form:

• ${\displaystyle AB\rightarrow AC}$
• ${\displaystyle AB\rightarrow CB}$
• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle A\rightarrow B}$
• ${\displaystyle A\rightarrow a}$

Where , and are variables and is a terminal symbol. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle a}$

For each context-sensitive grammar with a context-sensitive grammar exists in Kuroda normal form, generating the same language, that is, . ${\displaystyle G_{1}}$ ${\displaystyle \varepsilon \notin L(G_{1})}$ ${\displaystyle G_{2}}$ ${\displaystyle L(G_{1})=L(G_{2})}$

literature

• Benedek Nagy: Derivation Trees for Context-Sensitive Grammars . In: Automata, Formal Languages ​​and Algebraic Systems: Proceedings of AFLAS 2008 . World Scientific Pub Co, 2008, ISBN 981-4317-60-8 , pp. 182 ( limited preview in Google Book search).