请输入您要查询的字词:

 

单词 ChomskyHierarchy
释义

Chomsky hierarchy


The Chomsky hierarchy or Chomsky-Schützenberger hierarchy is a way of classifying formal grammars into four types, with the lower numbered types being more general.

Recall that a formal grammar G=(Σ,N,P,σ) consists of an alphabet Σ, an alphabet N of non-terminal symbols properly included in Σ, a non-empty finite setMathworldPlanetmath P of productions, and a symbol σN called the start symbol. The non-empty alphabet T:=Σ-N is the set of terminal symbols. Then G is called a

Type-0 grammar

if there are no restrictionsPlanetmathPlanetmathPlanetmath on the productions. Type-0 grammar is also known as an unrestricted grammar, or a phrase-structure grammar.

Type-1 grammar

if the productions are of the form uAvuWv, where u,v,WΣ* with Wλ, and AN, or σλ, provided that σ does not occur on the right hand side of any productions in P. As A is surrounded by words u,v, a type-1 grammar is also known as a context-sensitive grammar.

Type-2 grammar

if the productions are of the form AW, where AN and WΣ*. Type-2 grammars are also called context-free grammars, because the left hand side of any productions are “free” of contexts.

Type-3 grammar

if the productions are of the form Au or AuB, where A,BN and uT*. Owing to the fact that languagesPlanetmathPlanetmath generated by type-3 grammars can be represented by regular expressionsMathworldPlanetmath, type-3 grammars are also known as regular grammars.

It is clear that every type-i grammar is type-0, and every type-3 grammar is type-2. A type-2 grammar is not necessarily type-1, because it may contain both σλ and AW, where λ occurs in W. Nevertheless, the relevance of the hierarchy has more to do with the languages generated by the grammars. Call a formal language a type-i language if it is generated by a type-i grammar, and denote i the family of type-i languages. Then it can be shown that

3210

where each inclusion is strict.

Below is a table summarizing the four types of grammars, the languages they generate, and the equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath computational devices accepting the languages.

TitleChomsky hierarchy
Canonical nameChomskyHierarchy
Date of creation2013-03-22 16:27:04
Last modified on2013-03-22 16:27:04
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id13
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 68Q15
Classificationmsc 03D55
SynonymChomsky-Schützenberger hierarchy
SynonymChomsky-Schutzenberger hierarchy
Synonymunrestricted grammar
Definestype-0 grammar
Definestype-0 language
\\@unrecurse
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:13:31