# Kuroda normal form

**Kuroda normal form** is a restricted form of a formal grammar in which every production is one of three shapes: a pair of nonterminals rewritten as another pair, \( AB \to CD \); a nonterminal expanded to two nonterminals, \( A \to BC \); or a nonterminal rewritten as a single terminal, \( A \to a \), where \( A, B, C, D \) are nonterminal symbols and \( a \) is a terminal symbol.<sup>[1](https://planetmath.org/kurodanormalform)</sup> It is the standard normal form for context-sensitive grammars, playing the role that Chomsky normal form plays for context-free grammars, and it is named after Sige-Yuki Kuroda, who originally called grammars of this kind "linear bounded grammars", by analogy with the automaton that recognizes context-sensitive languages.<sup>[2](https://www.youtube.com/watch?v=ABPuinThYAs)</sup><sup> • </sup><sup>[3](https://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf)</sup>

| Key fact | Detail |
|---|---|
| Allowed productions | \( AB \to CD \), \( A \to BC \), and \( A \to a \); some authors add the unit rule \( A \to B \)<sup>[1](https://planetmath.org/kurodanormalform)</sup> |
| Empty-string case | For unrestricted (type-0) grammars the list gains \( A \to \varepsilon \); for monotone grammars \( S \to \lambda \) is allowed only when the start symbol \( S \) appears on no right-hand side<sup>[4](https://dspace.vut.cz/bitstreams/357c3077-1de7-4721-881c-51bff679fdeb/download)</sup><sup> • </sup><sup>[5](https://gyires.inf.unideb.hu/GyBITT/14/ch05.html)</sup> |
| Kuroda theorem | Every context-sensitive grammar has an equivalent context-sensitive grammar in Kuroda normal form<sup>[6](https://cs.brown.edu/courses/csci1810/fall-2024/resources/ch2_readings/automata_theory_and_formal_languages.pdf)</sup> |
| Characterization | Every length-increasing grammar has an equivalent grammar in Kuroda normal form<sup>[1](https://planetmath.org/kurodanormalform)</sup> |
| Origin | S.-Y. Kuroda, "Classes of languages and linear-bounded automata", *Information and Control* 7(2): 207–223, June 1964<sup>[7](https://www.scienceopen.com/document?vid=16a2eee2-26db-47f8-b6f1-12a728fc19b4)</sup> |
| One-sided variant | Penttonen normal form (one-sided normal form) restricts the context rule to \( AB \to AC \)<sup>[8](https://www.sciencedirect.com/science/article/pii/S0019995874910493)</sup> |

## Definition

A grammar \( G = (N, T, P, S) \) with nonterminals \( N \), terminals \( T \), productions \( P \), and start symbol \( S \) is in Kuroda normal form when every rule in \( P \) has one of the forms \( AB \to CD \), \( A \to BC \), or \( A \to a \), with \( A, B, C, D \in N \) and \( a \in T \).<sup>[1](https://planetmath.org/kurodanormalform)</sup> Some treatments add the unit production \( A \to B \); this rule is removable, since all occurrences of \( B \) can be replaced by \( A \) in every production of the grammar.<sup>[1](https://planetmath.org/kurodanormalform)</sup>

The exact list depends on the grammar class being normalized. For monotone grammars, the Debrecen textbook definition allows \( AB \to CD \), \( A \to BC \), \( A \to B \), \( A \to a \), and \( S \to \lambda \), with the condition that when \( S \to \lambda \) is present the start symbol occurs on no right-hand side; grammars in this form are monotone, that is, no rule shortens the sentential form.<sup>[5](https://gyires.inf.unideb.hu/GyBITT/14/ch05.html)</sup> For [unrestricted grammars](https://www.edgepedia.org/unrestricted-grammar), the form adds the erasing rule \( A \to \varepsilon \), giving the four shapes \( AB \to CD \), \( A \to BC \), \( A \to a \), and \( A \to \varepsilon \).<sup>[4](https://dspace.vut.cz/bitstreams/357c3077-1de7-4721-881c-51bff679fdeb/download)</sup><sup> • </sup><sup>[9](https://www.tutorialspoint.com/automata_theory/automata_theory_kuroda_normal_form.htm)</sup> A survey chapter of a formal language thesis defines the phrase-structure version with just \( A \to t \), \( A \to BC \), and \( AB \to CD \).<sup>[10](https://trepo.tuni.fi/bitstream/handle/10024/99577/978-952-03-0184-2.pdf)</sup>

## Existence theorems

The central result, usually called the Kuroda theorem, states that for every context-sensitive grammar there exists an equivalent context-sensitive grammar in Kuroda normal form.<sup>[6](https://cs.brown.edu/courses/csci1810/fall-2024/resources/ch2_readings/automata_theory_and_formal_languages.pdf)</sup> The proof is constructive: terminals are first removed from longer productions by introducing new variables with rules \( A \to a \), and further new variables are introduced to break up long blocks of nonterminals into pieces of length at most two.<sup>[11](https://www.cs.cmu.edu/~flac/pdf/lect-18.pdf)</sup> Levelt's 1974 textbook records that the normal-form theorem was first proven by Kuroda in 1964.<sup>[3](https://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf)</sup>

The form applies to length-increasing grammars, meaning grammars in which no derivation step shortens the string: every such grammar is equivalent to a grammar in Kuroda normal form, although a grammar that is equivalent to one in Kuroda normal form need not itself be length-increasing.<sup>[1](https://planetmath.org/kurodanormalform)</sup> Consequently every context-sensitive language that does not contain the empty string can be generated by a grammar in this form.<sup>[12](https://en.wiki.beta.math.wmflabs.org/wiki/Context-sensitive_grammar)</sup> The same construction extends upward: for every type-0 grammar an equivalent grammar can be effectively constructed whose rules have the forms \( A \to BC \), \( A \to a \), \( A \to \lambda \), and \( AB \to CD \), and a similar result holds for monotonous grammars with the \( A \to \lambda \) rules removed.<sup>[13](https://www.cs.auckland.ac.nz/~cristian/cca.pdf)</sup>

## One-sided and related forms

The two-sided context rule \( AB \to CD \) can be decomposed. A technique attributed to György Révész replaces \( AB \to CD \) by four context-sensitive rules, \( AB \to AZ \), \( AZ \to WZ \), \( WZ \to WD \), and \( WD \to CD \), using new nonterminals \( Z \) and \( W \); this also shows that every noncontracting grammar is context-sensitive.<sup>[2](https://www.youtube.com/watch?v=ABPuinThYAs)</sup> Among the four replacement rules, two preserve the left context and two preserve the right context, so a grammar in Kuroda normal form is equivalent to one whose productions are only \( A \to a \), \( A \to BC \), \( AB \to AC \), and \( AB \to CB \).<sup>[1](https://planetmath.org/kurodanormalform)</sup>

Dropping one side gives the one-sided normal form, also called Penttonen normal form, with productions \( AB \to AC \), \( A \to BC \), and \( A \to a \). Martti Penttonen, a Finnish mathematician, proved in 1974 that context-sensitive and one-sided context-sensitive languages coincide, yielding this normal form as a corollary.<sup>[8](https://www.sciencedirect.com/science/article/pii/S0019995874910493)</sup> As a consequence, every context-sensitive language not containing the empty word can be generated by a grammar in one-sided normal form.<sup>[1](https://planetmath.org/kurodanormalform)</sup> A survey of normal forms lists Kuroda and one-sided normal forms as the two principal normal forms for context-sensitive grammars, alongside Chomsky, Greibach, and operator normal forms for context-free grammars.<sup>[10](https://trepo.tuni.fi/bitstream/handle/10024/99577/978-952-03-0184-2.pdf)</sup>

## Uses

Normal forms restrict the shape of productions while preserving the generated language, a property called weak equivalence; they are used in studying syntactic properties of grammars, parsing theory, structural and descriptional complexity, and inference and learning theory.<sup>[10](https://trepo.tuni.fi/bitstream/handle/10024/99577/978-952-03-0184-2.pdf)</sup> For Kuroda normal form specifically, recognition becomes particularly simple: an algorithm first eliminates terminals and then operates only on pairs of consecutive variables.<sup>[11](https://www.cs.cmu.edu/~flac/pdf/lect-18.pdf)</sup> Levelt notes that the form is relevant both to the relationship between context-sensitive grammars and automata and to proofs of essential properties of transformational grammars.<sup>[3](https://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf)</sup>

## Origin

The form is named after Sige-Yuki Kuroda (1934–2009), a linguist at the [University of California, San Diego](https://www.edgepedia.org/university-of-california-san-diego), described in his department's bibliography as the founder of Japanese generative grammar.<sup>[14](https://dss-sites.ucsd.edu/kuroda/bibliography.html)</sup> His paper "Classes of languages and linear-bounded automata" appeared in *Information and Control*, volume 7, issue 2, pages 207–223, in June 1964.<sup>[7](https://www.scienceopen.com/document?vid=16a2eee2-26db-47f8-b6f1-12a728fc19b4)</sup> Grammars of the kind now called Kuroda normal form were called "linear bounded grammars" by Kuroda and several other authors, by analogy with the linear-bounded automaton, the machine model equivalent to context-sensitive grammars.<sup>[3](https://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf)</sup>

## References

1. [Kuroda normal form, PlanetMath](https://planetmath.org/kurodanormalform)
2. [Context Sensitive Grammar & Kuroda's Normal form, src7cse (YouTube)](https://www.youtube.com/watch?v=ABPuinThYAs)
3. [W. J. M. Levelt (1974). Formal Grammars in Linguistics and Psycholinguistics, Volume I, Mouton](https://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf)
4. [Normal forms for general grammars, Brno University of Technology](https://dspace.vut.cz/bitstreams/357c3077-1de7-4721-881c-51bff679fdeb/download)
5. [Context-Sensitive Languages, University of Debrecen, Formal Languages and Automata Theory](https://gyires.inf.unideb.hu/GyBITT/14/ch05.html)
6. [Alberto Pettorossi. Automata Theory and Formal Languages, Chapter 1 (Brown University course notes)](https://cs.brown.edu/courses/csci1810/fall-2024/resources/ch2_readings/automata_theory_and_formal_languages.pdf)
7. [S.-Y. Kuroda (1964). Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, ScienceOpen](https://www.scienceopen.com/document?vid=16a2eee2-26db-47f8-b6f1-12a728fc19b4)
8. [Martti Penttonen (1974). One-sided and two-sided context in formal grammars, Information and Control 25(4): 371–392](https://www.sciencedirect.com/science/article/pii/S0019995874910493)
9. [Kuroda Normal Form in Automata Theory, TutorialsPoint](https://www.tutorialspoint.com/automata_theory/automata_theory_kuroda_normal_form.htm)
10. [Elements of Formal Language Theory, Chapter 2, Tampere University](https://trepo.tuni.fi/bitstream/handle/10024/99577/978-952-03-0184-2.pdf)
11. [Lecture notes on context-sensitive grammars, Carnegie Mellon University (FLAC)](https://www.cs.cmu.edu/~flac/pdf/lect-18.pdf)
12. [Context-sensitive grammar, testwiki](https://en.wiki.beta.math.wmflabs.org/wiki/Context-sensitive_grammar)
13. [C. S. Calude, G. Păun. Computing with Cells and Atoms, prerequisites chapter](https://www.cs.auckland.ac.nz/~cristian/cca.pdf)
14. [S.-Y. Kuroda bibliography, UCSD](https://dss-sites.ucsd.edu/kuroda/bibliography.html)

---
*Topic: Encyclopedia › Society and history › Languages and linguistics › Linguistics › Formal and computational linguistics › Grammar normal forms and transformations*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 25, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 25, 2026 · Last review: Oct 25, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license