This HTML5 document contains 171 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbpedia-el	http://el.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-no	http://no.dbpedia.org/resource/
n36	http://bn.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-bg	http://bg.dbpedia.org/resource/
dbpedia-fi	http://fi.dbpedia.org/resource/
dbr	http://dbpedia.org/resource/
dbpedia-hr	http://hr.dbpedia.org/resource/
dbpedia-sh	http://sh.dbpedia.org/resource/
dbpedia-ar	http://ar.dbpedia.org/resource/
dbpedia-he	http://he.dbpedia.org/resource/
n18	http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbpedia-mk	http://mk.dbpedia.org/resource/
dcterms	http://purl.org/dc/terms/
dbpedia-cs	http://cs.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
dbpedia-kk	http://kk.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
n21	http://d-nb.info/gnd/
n16	http://dbpedia.org/resource/File:
dbp	http://dbpedia.org/property/
xsdh	http://www.w3.org/2001/XMLSchema#
dbpedia-uk	http://uk.dbpedia.org/resource/
dbpedia-la	http://la.dbpedia.org/resource/
dbo	http://dbpedia.org/ontology/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-sk	http://sk.dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
n50	http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/
dbc	http://dbpedia.org/resource/Category:
dbpedia-de	http://de.dbpedia.org/resource/
dbpedia-pl	http://pl.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
n53	https://www.sciencedirect.com/science/article/pii/S0019995859903626/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbpedia-ro	http://ro.dbpedia.org/resource/
wikidata	http://www.wikidata.org/entity/
gold	http://purl.org/linguistics/gold/
dbpedia-nl	http://nl.dbpedia.org/resource/
dbpedia-af	http://af.dbpedia.org/resource/
n54	https://global.dbpedia.org/id/
yago-res	http://yago-knowledge.org/resource/
dbpedia-it	http://it.dbpedia.org/resource/
dbpedia-ca	http://ca.dbpedia.org/resource/
prov	http://www.w3.org/ns/prov#
n43	http://bs.dbpedia.org/resource/
dbpedia-nn	http://nn.dbpedia.org/resource/
foaf	http://xmlns.com/foaf/0.1/
dbpedia-simple	http://simple.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
dbpedia-ko	http://ko.dbpedia.org/resource/
n39	https://archive.org/details/
dbpedia-fa	http://fa.dbpedia.org/resource/
n40	https://archive.org/details/computabilitycom00davi_405/page/
dbpedia-es	http://es.dbpedia.org/resource/
freebase	http://rdf.freebase.com/ns/
owl	http://www.w3.org/2002/07/owl#
dbpedia-ka	http://ka.dbpedia.org/resource/

Statements

Subject Item

dbr:Chomsky_hierarchy

rdf:type

owl:Thing dbo:Software yago:WikicatFormalLanguages yago:Communication100033020 yago:Abstraction100002137 yago:Language106282651

rdfs:label

Chomsky hierarchy Hierarquia de Chomsky Ієрархія Чомскі Chomskyhiërarchie Chomského hierarchie Ιεραρχία Τσόμσκι チョムスキー階層 Gerarchia di Chomsky Hierarchia Chomsky’ego Jerarquía de Chomsky Hiérarchie de Chomsky طبقات اللغات الصورية Jerarquia de Chomsky Chomsky-Hierarchie 乔姆斯基谱系 Иерархия Хомского 촘스키 위계

rdfs:comment

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. 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: 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. To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η ιεραρχία Τσόμσκι, όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της επιστήμης υπολογιστών. 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. 촘스키 위계(Chomsky hierarchy)는 형식 언어를 생성하는 형식 문법의 클래스 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다. Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским. 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. Ієра́рхія Чо́мскі, або Ієра́рхія Чо́мскі-Шутценбе́рґера (названа на честь мовознавця Ноама Чомскі та математика ) — поняття в теоретичній інформатиці, яким позначають ієрархію формальних граматик, які породжують формальні мови. Вперше описана Ноамом Чомскі в 1956 році. Чотири описані Чомскі типи граматик виходять від базової, необмеженої граматики (граматика типу 0), на яку послідовно накладають обмеження на правила продукції. В залежності від типу найпростішої граматики, яка може згенерувати задану формальну мову, формальні мови ділять на відповідні категорії від типу 0 до типу 3. 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. 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次： * 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。 * 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。 * 2-型文法（上下文无关文法）生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。 * 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。 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. チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。 تنقسم اللغات الصورية إلى أربع طبقات بالنسبة إلى النحو الصوري. الأولى اللغات القياسية ثم اللغات المطلقة ثم المقيدة ثم المحصورة. 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 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. 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.

foaf:depiction

n18:Chomsky-hierarchy.svg

dcterms:subject

dbc:Generative_linguistics dbc:Noam_Chomsky dbc:1956_in_computing dbc:Formal_languages

dbo:wikiPageID

6011

dbo:wikiPageRevisionID

1105404032

dbo:wikiPageWikiLink

dbr:Turing_machine dbc:Noam_Chomsky dbc:Generative_linguistics n16:Chomsky-hierarchy.svg dbc:1956_in_computing dbr:Recursively_enumerable_language dbr:Deterministic_context-free_language dbr:Colorless_green_ideas_sleep_furiously dbr:Recursive_language dbr:Unrestricted_grammar dbr:Computer_science dbr:Regular_grammar dbr:Finite_state_automaton dbr:Regular_language dbr:Scope_(computer_science) dbr:Linear_bounded_automaton dbr:Machine_that_always_halts dbr:Noam_Chomsky dbr:LL_parser dbr:Terminal_symbol dbr:Nonterminal_symbol dbr:Linguistics dbr:String_(computer_science) dbr:Formal_language dbr:Regular_expression dbr:Formal_grammar dbr:Marcel-Paul_Schützenberger dbr:Natural_language dbr:Context-sensitive_grammar dbr:Context-sensitive_language dbr:Name_resolution_(programming_languages) dbr:Context-free_language dbr:Programming_language dbr:Phrase_structure_grammar dbr:Phrase_structure_rules dbr:Pushdown_automaton dbr:English_language dbr:Context-free_grammar dbr:Containment_hierarchy dbc:Formal_languages dbr:Production_(computer_science) dbr:Axiom_schema

dbo:wikiPageExternalLink

n39:computabilitycom00davi_405 n40:n345 n50:1963-7ChomskyAlgebraic.pdf n53:pdf%3Fmd5=9d466f851651bd592afa5ee561b7a0b0&pid=1-s2.0-S0019995859903626-main.pdf%7Cdoi-access=free

owl:sameAs

dbpedia-he:ההיררכיה_של_חומסקי dbpedia-de:Chomsky-Hierarchie dbpedia-sk:Chomského_hierarchia wikidata:Q190913 dbpedia-ka:ჩომსკის_იერარქია dbpedia-simple:Chomsky_hierarchy dbpedia-it:Gerarchia_di_Chomsky n21:4529323-5 dbpedia-pl:Hierarchia_Chomsky’ego dbpedia-fa:وراثت_چامسکی dbpedia-sr:Hijerarhija_Čomskog dbpedia-uk:Ієрархія_Чомскі dbpedia-es:Jerarquía_de_Chomsky dbpedia-fr:Hiérarchie_de_Chomsky dbpedia-ro:Ierarhia_Chomsky freebase:m.01t30 dbpedia-ca:Jerarquia_de_Chomsky dbpedia-kk:Хомский_иерархиясы dbpedia-fi:Chomskyn_hierarkia dbpedia-bg:Йерархия_на_Чомски dbpedia-af:Chomsky-hiërargie dbpedia-ja:チョムスキー階層 n36:চম্‌স্কি_স্তরক্রম dbpedia-ko:촘스키_위계 yago-res:Chomsky_hierarchy n43:Chomskyjeva_hijerarhija dbpedia-el:Ιεραρχία_Τσόμσκι dbpedia-pt:Hierarquia_de_Chomsky dbpedia-zh:乔姆斯基谱系 dbpedia-nn:Chomskyhierarkiet dbpedia-cs:Chomského_hierarchie dbpedia-la:Hierarchia_Chomskiana dbpedia-mk:Хиерархија_на_Чомски n54:pz9f dbpedia-sh:Chomskyjeva_hijerarhija dbpedia-nl:Chomskyhiërarchie dbpedia-ar:طبقات_اللغات_الصورية dbpedia-ru:Иерархия_Хомского dbpedia-no:Chomskyhierarkiet dbpedia-hr:Chomskyjeva_hijerarhija

dbp:wikiPageUsesTemplate

dbt:Math dbt:Reflist dbt:Authority_control dbt:Cite_journal dbt:Sans-serif dbt:Cite_book dbt:Formal_languages_and_grammars dbt:Cleanup_section dbt:Noam_Chomsky dbt:Short_description dbt:Main_article dbt:Main dbt:Mset dbt:Mvar

dbo:thumbnail

n18:Chomsky-hierarchy.svg?width=300

dbp:date

June 2022

dbp:reason

All these "type" sections would benefit from examples

dbo:abstract

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. 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次： * 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。 * 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。 * 2-型文法（上下文无关文法）生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。 * 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。 正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。 下表总结了上述四种类型的文法的主要特点： تنقسم اللغات الصورية إلى أربع طبقات بالنسبة إلى النحو الصوري. الأولى اللغات القياسية ثم اللغات المطلقة ثم المقيدة ثم المحصورة. 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. 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. 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. 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. Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским. 촘스키 위계(Chomsky hierarchy)는 형식 언어를 생성하는 형식 문법의 클래스 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다. Ієра́рхія Чо́мскі, або Ієра́рхія Чо́мскі-Шутценбе́рґера (названа на честь мовознавця Ноама Чомскі та математика ) — поняття в теоретичній інформатиці, яким позначають ієрархію формальних граматик, які породжують формальні мови. Вперше описана Ноамом Чомскі в 1956 році. Чотири описані Чомскі типи граматик виходять від базової, необмеженої граматики (граматика типу 0), на яку послідовно накладають обмеження на правила продукції. В залежності від типу найпростішої граматики, яка може згенерувати задану формальну мову, формальні мови ділять на відповідні категорії від типу 0 до типу 3. 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. チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。 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. 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. 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. To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η ιεραρχία Τσόμσκι, όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της επιστήμης υπολογιστών. 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.

gold:hypernym

dbr:Hierarchy

prov:wasDerivedFrom

wikipedia-en:Chomsky_hierarchy?oldid=1105404032&ns=0

dbo:wikiPageLength

13082

foaf:isPrimaryTopicOf

wikipedia-en:Chomsky_hierarchy