Kuroda normal form

Kuroda normal form

In formal language theory, a grammar is in Kuroda normal form "iff" all production rules are of the form::"AB → CD" or:"A → BC" or:"A → B" or:"A → α"where A, B, C and D are nonterminal symbols and α is a terminal symbol.

Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.

ee also

*Backus-Naur form
*Chomsky normal form
*Greibach normal form

References

* S.-Y. Kuroda, "Classes of languages and linear-bounded automata", "Information and Control", 7(2): 207–223, June 1964.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… …   Wikipedia

  • Chomsky normal form — In computer science, a context free grammar is said to be in Chomsky normal form if all of its production rules are of the form: or or where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S …   Wikipedia

  • Greibach normal form — In computer science, to say that a context free grammar is in Greibach normal form (GNF) means that all production rules are of the form::A o alpha X or:S o lambdawhere A is a nonterminal symbol, α is a terminal symbol, X is a (possibly empty)… …   Wikipedia

  • Kuroda — (黒田) is a Japanese surname.People*Aki Kuroda (黒田アキ or 黒田明比古) (born 1944), Japanese painter *Chris Kuroda, former lighting designer / operator for the band Phish *Emily Kuroda, actress *Fukumi Kuroda (黒田 福美) (born 1956), Japanese actress *Hiroki… …   Wikipedia

  • Noncontracting grammar — Contents 1 Formal definition 2 Example 3 Equivalent types of grammars; expressive power 4 See also Formal definition …   Wikipedia

  • Context-sensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… …   Wikipedia

  • Curry–Howard correspondence — A proof written as a functional program: the proof of commutativity of addition on natural numbers in the proof assistant Coq. nat ind stands for mathematical induction, eq ind for substitution of equals and f equal for taking the same function… …   Wikipedia

  • Black Moon Clan — Sailor Moon villain group The Black Moon Clan. Down left side: Venetici, Aquatici, Chiral, Achiral. Center square, from top left: Blue Saphir, Prince Demand, Green Esmeraude, Crimson Rubeus. Right: Wiseman. Bottom line, from left: Kōan, Bertier,… …   Wikipedia

  • List of Bobobo-bo Bo-bobo characters — The universe of the anime and manga series Bobobo bo Bo bobo is a home to a wide array of fictional characters. Contents 1 Main characters 1.1 Bobobo bo Bo bobo 1.2 Beauty 1.3 …   Wikipedia

  • Imagin — For the animation studio of the same name, see Imagin (studio). The Imagin (イマジン, Imajin?) are a fictional race that serve as the antagonists in the Kamen Rider Series Kamen Rider Den O. The name Imagin comes from several words in the English,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”