| dbo:abstract
|
- تنقسم اللغات الصورية إلى أربع طبقات بالنسبة إلى النحو الصوري. الأولى اللغات القياسية ثم اللغات المطلقة ثم المقيدة ثم المحصورة. (ar)
- Dins de les ciències de la computació, i en l'àrea dels llenguatges de programació, la jerarquia de Chomsky (també coneguda com a 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 de , que va desenvolupar la teoria dels llenguatges formals. (ca)
- 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 (frázové/neomezené gramatiky)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. V případě, že je jazyk generován úplným Turingovým strojem ( Turingův stroj akceptuje nebo zamítá), je tento jazyk nazýván jako rekurzivní.Gramatiky typu 1 (kontextové gramatiky, Context-sensitive, CSG)Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel , kde je neterminál a jsou řetězce terminálů a neterminálů, přičemž je neprázdný ( a prázdné být mohou). Pravidlo je povoleno, pokud se 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 (bezkontextové gramatiky)Generují bezkontextové jazyky. Skládají se z pravidel s neterminálem a řetězcem terminálů a neterminálů . Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým zásobníkovým automatem.Upřesnění: Gramatiky typu 2 mohou obsahovat pravidla. Přesto jsou jimi generované jazyky podmnožinou jazyků generovaných gramatikami typu 1, protože existuje algoritmus na převod libovolné gramatiky typu 2 na gramatiku bez pravidel.Gramatiky typu 3 (regulární gramatiky)Generují regulární jazyky. Pravidla těchto gramatik jsou omezena na jeden neterminál na levé straně. Pravá strana se skládá z terminálu, který může být následován jedním neterminálem (tedy pravidla a , kde ). Tyto gramatiky se také nazývají pravolineární. Obdobně se definují i levolineární gramatiky, kde může být na pravé straně pravidel jeden terminál předcházen jedním neterminálem. Nikdy se však nesmí vyskytovat v jedné gramatice zároveň pravidla jak z pravolineární gramatiky, tak z levolineární. Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní. Pravidlo je povoleno, pokud se nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné konečným automatem. (cs)
- To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η ιεραρχία Τσόμσκι, όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της επιστήμης υπολογιστών. (el)
- In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the 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. (en)
- 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. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind; bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt. Grammatiken niedrigeren Typs sind erzeugungsmächtiger als die höherer Typen. Eine Sprache, die von einer Grammatik des Typs k erzeugt wird, heißt eine Sprache des Typs k. Neben die Chomsky-Hierarchie der Grammatiken tritt in diesem Sinne eine Chomsky-Hierarchie der Sprachen. (de)
- En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. (fr)
- En lingüística la jerarquía de Chomsky (ocasionalmente también llamada la jerarquía de Chomsky–Schützenberger) 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. (es)
- 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. Elke klasse in de chomskyhiërarchie omvat ook de klassen met een hoger nummer. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky, en werd het eerst beschreven in 1956. (nl)
- 촘스키 위계(Chomsky hierarchy)는 형식 언어를 생성하는 형식 문법의 클래스 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다. (ko)
- 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. (it)
- チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。 (ja)
- Hierarchia Chomsky’ego – 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. Każdy język określonej klasy należy jednocześnie do każdej klasy poniżej, czyli:
* Każdy język regularny jest także bezkontekstowy.
* Każdy język bezkontekstowy jest także kontekstowy.
* Każdy język kontekstowy jest rekurencyjnie przeliczalny. Zostało także udowodnione, że istnieje teoretyczny algorytm, który jest w stanie przekształcić daną gramatykę formalną w leżącą niżej w hierarchii. (pl)
- 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 (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica. 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. (pt)
- Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским. (ru)
- 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次：
* 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
* 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
* 2-型文法（上下文无关文法）生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
* 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。 正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。 下表总结了上述四种类型的文法的主要特点： (zh)
- Ієра́рхія Чо́мскі, або Ієра́рхія Чо́мскі-Шутценбе́рґера (названа на честь мовознавця Ноама Чомскі та математика ) — поняття в теоретичній інформатиці, яким позначають ієрархію формальних граматик, які породжують формальні мови. Вперше описана Ноамом Чомскі в 1956 році. Чотири описані Чомскі типи граматик виходять від базової, необмеженої граматики (граматика типу 0), на яку послідовно накладають обмеження на правила продукції. В залежності від типу найпростішої граматики, яка може згенерувати задану формальну мову, формальні мови ділять на відповідні категорії від типу 0 до типу 3. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13082 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:reason
|
- All these "type" sections would benefit from examples (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- تنقسم اللغات الصورية إلى أربع طبقات بالنسبة إلى النحو الصوري. الأولى اللغات القياسية ثم اللغات المطلقة ثم المقيدة ثم المحصورة. (ar)
- Dins de les ciències de la computació, i en l'àrea dels llenguatges de programació, la jerarquia de Chomsky (també coneguda com a 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 de , que va desenvolupar la teoria dels llenguatges formals. (ca)
- To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η ιεραρχία Τσόμσκι, όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της επιστήμης υπολογιστών. (el)
- In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the 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. (en)
- En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. (fr)
- En lingüística la jerarquía de Chomsky (ocasionalmente también llamada la jerarquía de Chomsky–Schützenberger) 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. (es)
- 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. Elke klasse in de chomskyhiërarchie omvat ook de klassen met een hoger nummer. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky, en werd het eerst beschreven in 1956. (nl)
- 촘스키 위계(Chomsky hierarchy)는 형식 언어를 생성하는 형식 문법의 클래스 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다. (ko)
- 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. (it)
- チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。 (ja)
- Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским. (ru)
- Ієра́рхія Чо́мскі, або Ієра́рхія Чо́мскі-Шутценбе́рґера (названа на честь мовознавця Ноама Чомскі та математика ) — поняття в теоретичній інформатиці, яким позначають ієрархію формальних граматик, які породжують формальні мови. Вперше описана Ноамом Чомскі в 1956 році. Чотири описані Чомскі типи граматик виходять від базової, необмеженої граматики (граматика типу 0), на яку послідовно накладають обмеження на правила продукції. В залежності від типу найпростішої граматики, яка може згенерувати задану формальну мову, формальні мови ділять на відповідні категорії від типу 0 до типу 3. (uk)
- 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 (frázové/neomezené gramatiky)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. V případě, že je jazyk generován úplným Turingovým strojem ( Turingův stroj akceptuje nebo zamítá), je tento jazyk nazýván jako rekurzivní.Gramatiky typu 1 (kontextové gramatiky, Context-sensitive, CSG)Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel , kde je neterminál a jsou řetězce terminálů a neterminálů, přičemž je neprázdný ( a prázdné být mohou). Pravid (cs)
- 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. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind; bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt. (de)
- Hierarchia Chomsky’ego – 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. Każdy język określonej klasy należy jednocześnie do każdej klasy poniżej, czyli: (pl)
- 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 (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica. (pt)
- 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次：
* 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
* 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
* 2-型文法（上下文无关文法）生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
* 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。 (zh)
|
| rdfs:label
|
- طبقات اللغات الصورية (ar)
- Jerarquia de Chomsky (ca)
- Chomského hierarchie (cs)
- Chomsky-Hierarchie (de)
- Ιεραρχία Τσόμσκι (el)
- Chomsky hierarchy (en)
- Jerarquía de Chomsky (es)
- Hiérarchie de Chomsky (fr)
- Gerarchia di Chomsky (it)
- 촘스키 위계 (ko)
- チョムスキー階層 (ja)
- Chomskyhiërarchie (nl)
- Hierarchia Chomsky’ego (pl)
- Hierarquia de Chomsky (pt)
- Иерархия Хомского (ru)
- Ієрархія Чомскі (uk)
- 乔姆斯基谱系 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
