| dbpprop:abstract
|
- Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956. It is also named after Marcel-Paul Schützenberger who played a crucial role in the development of the theory of formal languages.
- Chomsky-Hierarchie, gelegentlich Chomsky–Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen. Sie wurde 1956 erstmals von Noam Chomsky beschrieben. Die vier von Chomsky beschriebenen Grammatiktypen entstehen dabei ausgehend von einer nicht eingeschränkten Grundgrammatik (der Typ-0-Grammatik) indem zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden. Entsprechend des Typs einer Grammatik, die mindestens erforderlich ist, um eine bestimmte formale Sprache zu erzeugen, werden auch formale Sprachen in dieselben Kategorien von Typ 0 bis Typ 3 eingeteilt.
- Dins de les ciències de la computació, i en l'àrea dels llenguatges de programació, la jerarquia de Chomsky (també coneguda com Jerarquia de Chomsky-Schützenberger) és una classificació jeràrquica de classes de gramàtiques formals que generen llenguatges formals. Aquesta jerarquia de gramàtiques fou proposta per Noam Chomsky l'any 1956. També s'anomena en honor a Marcel-Paul Schützenberger, que va desenvolupar la teoria dels llenguatges formals.
- Chomského hierarchie je hierarchie tříd formálních gramatik generujících formální jazyky. Byla vytvořena Noamem Chomskym v roce 1956. Chomského hierarchie se skládá z následujících tříd: Gramatiky typu 0 Zahrnují v sobě všechny formální gramatiky, generují právě ty jazyky, které mohou být rozpoznané nějakým Turingovým strojem. Tyto jazyky se někdy nazývají rekurzivně spočetné jazyky. Gramatiky typu 1 Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>, kde <math>A</math> je neterminál a <math>\alpha</math>, <math>\beta</math> a <math>\gamma</math> řetězce terminálů a neterminálů. Řetězce <math>\alpha</math> a <math>\beta</math> mohou být prázdné, ale <math>\gamma</math> musí být neprázdná. Pravidlo <math>S \rightarrow \epsilon</math> je povoleno, pokud se <math>S</math> nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné lineárně ohraničeným Turingovým strojem. Gramatiky typu 2 Generují bezkontextové jazyky. Skládají se z pravidel <math>A \rightarrow \gamma</math> s neterminálem <math>A</math> a řetězcem terminálů a neterminálů <math>\gamma</math>. Pravidlo <math>S \rightarrow \epsilon</math> je povoleno, pokud se <math>S</math> nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým zásobníkovým automatem. Gramatiky typu 3 Generují regulární jazyky. Pravidla těchto gramatik jsou omezena na jeden neterminál na levé straně. Pravá strana se skládá z řetězce terminálů, který může být následován jedním neterminálem. Tyto gramatiky se také nazývají pravé lineární gramatiky. Obdobně se definují i levé lineární gramatiky, kde může být na pravé straně pravidel řetězec terminálů předcházen jedním neterminálem. Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní. Regulární gramatika je ve standardní formě, pokud je pravá strana tvořena jedním terminálem následovaným jedním neterminálem nebo pokud je pravá strana prázdné slovo. Tyto jazyky jsou právě jazyky rozpoznatelné konečným automatem. Přičemž platí, že každý regulární jazyk je také bezkontextový, každý bezkontextový jazyk je také kontextový, každý kontextový jazyk je také rekurzivně spočetný – jak je naznačeno na obrázku. Navíc všechny inkluze jsou oprávněné, tedy existují rekurzivně spočetné jazyky, které nejsou rekurzivní, rekurzivní jazyky, které nejsou kontextové, kontextové jazyky, které nejsou bezkontextové a bezkontextové jazyky, které nejsou regulární.
- En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
- Chomskyn hierarkia on tunnetuin järjestelmä formaaleja kieliä tuottavien formaalien kielioppien luokittelemiseen. Kieliopit muodostavat järjestelmässä hierarkian, jossa yksinkertaisempi kielioppi on myös yleisemmän luokan mukainen kielioppi. Hierarkian portaat ovat: Säännölliset kielet (Regular languages), jotka voidaan tunnistaa äärellisillä automaateilla. Yksinkertaisin luokka. Yhteydettömät kielet (yhteysriippumattomat tai kontekstittomat kielet, Context-free languages), tunnistamiseen riittää pinoautomaatti. Yhteysherkät kielet (kontekstiherkät kielet, Context-sensitive languages), voidaan tunnistaa lineaarisesti rajoitetulla automaatilla. Rekursiivisesti numeroituvat kielet (rekursiivisesti lueteltavat kielet tai yleiset kielet, Recursively enumerable languages), voidaan tunnistaa Turingin koneella. Yleisin luokka. Suomennokset ovat vakiintumattomia. Chomskyn hierarkia on nimetty sen kehittäjän, amerikkalaisen kielitieteilijän professori Noam Chomskyn mukaan.
- La hiérarchie de Chomsky est une classification naturelle (non arbitraire) des langages décrits par les grammaires formelles, découverte en 1956 par le linguiste Noam Chomsky. Tout langage pouvant être généré ou accepté par un système formel (logico-mathématique) peut se définir à l’aide d’une de ces grammaires. Tout système formel pouvant être utilisé pour générer ou accepter un langage quelconque est strictement équivalent à l’une des grammaires formelles de Chomsky. La hiérarchie de Chomsky constitue le résultat le plus important de la branche primordiale de l’informatique théorique qu’est la théorie des automates. Chaque niveau de grammaire est strictement isomorphe à un type particulier d’automate, le niveau zéro correspondant aux machines de Turing, c’est-à-dire à la puissance de calcul des ordinateurs. La thèse de Church-Turing postule qu’il est impossible de créer une grammaire plus puissante. Ces travaux sont largement utilisés en informatique, en particulier pour la conception d’interpréteurs ou de compilateurs, ou encore pour l’analyse des langages naturels.
- La gerarchia di Chomsky è un insieme di classi di grammatiche formali che generano linguaggi formali. La gerarchia di queste grammatiche, chiamate anche grammatiche a struttura sintagmatica (phrase structure grammars), fu descritta da Noam Chomsky nel 1956.
- チョムスキー階層（-かいそう、Chomsky Hierarchy）とは、形式言語を生成する形式文法のクラスの包含階層である。これは「句構造文法」（Phrase Structure Grammars）の階層とも呼ばれ、1956年にノーム・チョムスキーが発表した。
- De Chomskyhiërarchie is een indeling in klassen van de formele talen naar het type formele grammatica dat alle talen binnen een bepaalde klasse kan genereren. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky. zij is het eerst beschreven in een publicatie uit 1956 Normaal gesproken behoren onberekenbare talen niet tot de Chomskyhiërarchie, maar het is wel onderwerp van discussie of talen onberekenbaar kunnen zijn.
- Hierarchia Chomsky'ego to stworzona przez Noama Chomsky'ego hierarchia klas języków formalnych. Hierarchia składa się z czterech klas: języki typu 3 - regularne języki typu 2 - bezkontekstowe języki typu 1 - kontekstowe języki typu 0 - rekurencyjnie przeliczalne Język należy do danej klasy wtedy i tylko wtedy, gdy jest możliwe zbudowanie gramatyki formalnej, która generuje dany język, a której reguły nie wykraczają poza ograniczenia dla danej klasy.
- Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma linguagem de tipo n - 1.
- Ierarhia Chomsky este o ierarhie de incluziune a claselor de gramatici formale care generează limbaje formale. Ierarhia acestor gramatici, numite şi gramatici de structură a frazelor, a fost descrise de Noam Chomsky în 1956.
- Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачуссетского технологического института, лингвистом Ноамом Хомским.
- 乔姆斯基体系是刻画形式文法表达能力的一个分类谱系，是由诺姆·乔姆斯基于1956年提出的。它包括四个层次： 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。 2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。 正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。 下表总结了上述四种类型的文法的主要特点：
|
| rdfs:comment
|
- Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956. It is also named after Marcel-Paul Schützenberger who played a crucial role in the development of the theory of formal languages.
- Chomsky-Hierarchie, gelegentlich Chomsky–Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen. Sie wurde 1956 erstmals von Noam Chomsky beschrieben.
- Dins de les ciències de la computació, i en l'àrea dels llenguatges de programació, la jerarquia de Chomsky (també coneguda com Jerarquia de Chomsky-Schützenberger) és una classificació jeràrquica de classes de gramàtiques formals que generen llenguatges formals. Aquesta jerarquia de gramàtiques fou proposta per Noam Chomsky l'any 1956. També s'anomena en honor a Marcel-Paul Schützenberger, que va desenvolupar la teoria dels llenguatges formals.
- Chomského hierarchie je hierarchie tříd formálních gramatik generujících formální jazyky. Byla vytvořena Noamem Chomskym v roce 1956. Chomského hierarchie se skládá z následujících tříd: Gramatiky typu 0 Zahrnují v sobě všechny formální gramatiky, generují právě ty jazyky, které mohou být rozpoznané nějakým Turingovým strojem. Tyto jazyky se někdy nazývají rekurzivně spočetné jazyky. Gramatiky typu 1 Generují kontextové jazyky.
- En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
- Chomskyn hierarkia on tunnetuin järjestelmä formaaleja kieliä tuottavien formaalien kielioppien luokittelemiseen. Kieliopit muodostavat järjestelmässä hierarkian, jossa yksinkertaisempi kielioppi on myös yleisemmän luokan mukainen kielioppi. Hierarkian portaat ovat: Säännölliset kielet (Regular languages), jotka voidaan tunnistaa äärellisillä automaateilla. Yksinkertaisin luokka.
- La hiérarchie de Chomsky est une classification naturelle (non arbitraire) des langages décrits par les grammaires formelles, découverte en 1956 par le linguiste Noam Chomsky. Tout langage pouvant être généré ou accepté par un système formel (logico-mathématique) peut se définir à l’aide d’une de ces grammaires. Tout système formel pouvant être utilisé pour générer ou accepter un langage quelconque est strictement équivalent à l’une des grammaires formelles de Chomsky.
- La gerarchia di Chomsky è un insieme di classi di grammatiche formali che generano linguaggi formali. La gerarchia di queste grammatiche, chiamate anche grammatiche a struttura sintagmatica (phrase structure grammars), fu descritta da Noam Chomsky nel 1956.
- チョムスキー階層（-かいそう、Chomsky Hierarchy）とは、形式言語を生成する形式文法のクラスの包含階層である。これは「句構造文法」（Phrase Structure Grammars）の階層とも呼ばれ、1956年にノーム・チョムスキーが発表した。
- De Chomskyhiërarchie is een indeling in klassen van de formele talen naar het type formele grammatica dat alle talen binnen een bepaalde klasse kan genereren. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky. zij is het eerst beschreven in een publicatie uit 1956 Normaal gesproken behoren onberekenbare talen niet tot de Chomskyhiërarchie, maar het is wel onderwerp van discussie of talen onberekenbaar kunnen zijn.
- Hierarchia Chomsky'ego to stworzona przez Noama Chomsky'ego hierarchia klas języków formalnych. Hierarchia składa się z czterech klas: języki typu 3 - regularne języki typu 2 - bezkontekstowe języki typu 1 - kontekstowe języki typu 0 - rekurencyjnie przeliczalne Język należy do danej klasy wtedy i tylko wtedy, gdy jest możliwe zbudowanie gramatyki formalnej, która generuje dany język, a której reguły nie wykraczają poza ograniczenia dla danej klasy.
- Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3.
- Ierarhia Chomsky este o ierarhie de incluziune a claselor de gramatici formale care generează limbaje formale. Ierarhia acestor gramatici, numite şi gramatici de structură a frazelor, a fost descrise de Noam Chomsky în 1956.
- Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачуссетского технологического института, лингвистом Ноамом Хомским.
|
![[RDF Data]](/statics/sw-cube.png)
