Ієра́рхія Чо́мскі, або Ієра́рхія Чо́мскі-Шутценбе́рґера (названа на честь мовознавця Ноама Чомскі та математика ) — поняття в теоретичній інформатиці, яким позначають ієрархію формальних граматик, які породжують формальні мови. Вперше описана Ноамом Чомскі в 1956 році. Чотири описані Чомскі типи граматик виходять від базової, необмеженої граматики (граматика типу 0), на яку послідовно накладають обмеження на правила продукції.
В залежності від типу найпростішої граматики, яка може згенерувати задану формальну мову, формальні мови ділять на відповідні категорії від типу 0 до типу 3.
Вступ
Формальні мови відіграють в інформатиці важливу роль. Завдяки ним, інформацію можна представляти у вигляді, придатному для автоматичного аналізу та обробки на комп'ютері. Формальні мови в дечому подібні до природних. Вони складаються з множини так званих термінальних символів (їм відповідають склади в природних мовах), які можна складати в слова. Крім того, задані правила (їх називають граматикою), які вказують способи побудови виразів на основі слів (вирази аналогічні реченням природної мови). Наведені приклади не свідчать про повну ідентичність, а лише вказують на основну ідею поняття. Серед прикладів застосування формальних мов можна назвати мови програмування або мови розмітки даних, наприклад, XML або HTML. Слід звернути увагу на те, що формальні мови визначають лише спосіб представлення даних (наприклад, те, що XML-дані побудовані з вкладених тегів), але не самі дані.
Ідея формальних мов полягає в створенні точного математичного опису для подібних мов. На основі цього опису можна будувати засоби для автоматичної обробки цих мов (так звані синтаксичні аналізатори). В попередньому абзаці вже названо основні складові формальної мови. Також слід додати множину основних символів — алфавіт. Алфавіт зазвичай позначають , і може складатись, наприклад, зі звичних літер, цифр тощо. Ще однією складовою формальної мови є граматика. Граматики задають правилами підстановки виду α → β. За цим правилом можна замінити дійсне слово позначене як α на слово позначене як β та отримати дійсне слово мови. На додачу, задають початковий символ, часто як аксіому. Початковий символ, за визначенням, є словом з мови. Також слід відрізняти та нетермінальні символи. Строго кажучи, слова та речення формальної мови можуть складатись лише з термінальних символів (наприклад, літери алфавіту). Нетермінальні символи (також називають змінними) відповідають, певним чином, деякому поняттю. В наступному прикладі описано мову, яка породжує математичні вирази (суми). Термінальні символи підкреслені, а нетермінальні виділено курсивом. Кожен рядок визначає одне правило.
- Сума → Цифра
- Сума → Сума + Цифра
- Сума → Сума - Цифра
- Цифра → 1..9
Аксіомою в цій мові є Сума. Виходячи з неї, застосуванням наведених вище правил, можна отримати необхідний вираз:
Сума | Аксіома |
Сума − Цифра | Застосовано 3 правило |
Сума + Цифра − Цифра | Застосовано 2 правило |
Цифра + Цифра − Цифра | Застосовано 1 правило |
1 + Цифра − Цифра | Застосовано 4 правило |
1 + 2 − Цифра | Застосовано 4 правило |
1 + 2 − 9 | Застосовано 4 правило |
Порядок застосування правил довільний. Граматика визначає лише правила, які дозволено використовувати у поточній ситуації, і не дає вказівки, які правила мають бути застосовані. Наприклад, до першого речення можна застосувати правила 1—3, та не можна застосувати 4 правило. Починаючи з 4 речення можливе застосування лише 4 правила.
Формальні граматики дозволяють описувати складніші формальні мови. Наприклад, синтаксис мови програмування Паскаль визначено у вигляді формальної граматики.
Ієрархія Чомскі намагається класифікувати необмежені, в принципі, мови, символьні вирази та правила. Для цього запроваджують певні класи мов, для яких можливо встановити швидкодію та підхід до комп'ютерної обробки. Крім того, мови тим більше обмежені, чим глибше знаходяться в ієрархії. Взагалі, можна помітити, що простіші мови, з одного боку, простіше піддаються комп'ютерній обробці, а з іншого — їм бракує виразності. Наприклад, для пошуку деяких шаблонів у тексті використовують регулярні вирази. Регулярні вирази відповідають граматикам Чомскі типу 3. Просто їхньої виразності досить, аби шукати різноманітні фрагменти тексту, але їх не достатньо, для, наприклад, описання мов програмування. Для описання мов програмування використовують, зазвичай, граматики типу 2.
Огляд
Далі позначатимемо формальну граматику G = (N, Σ, P, S). Так, N означатиме множину нетермінальних символів, Σ множину термінальних символів, P множину правил виводу та S початковий символ.
В наступній таблиці наведено огляд чотирьох типів формальних граматик, правил виводу, формальних мов та автомати, здатні їх розпізнати.
Граматика | Правила | Мови | Автомати | Скорочення |
---|---|---|---|---|
Тип-0 Довільна формальна граматика | α → β α ∈ V* N V*, β ∈ V* | Машина Тюринга | KSV* | |
Тип-1 Контекстно-залежна граматика | α A β → α'γ'β A ∈ N, α, β ∈ V*, γ ∈ V+ | КЗ | ||
Тип-2 Контекстно-вільна граматика | A → γ A ∈ N, γ ∈ V* | контекстно-вільна | недетермінований автомат з магазинною пам'ятю | КВ |
Тип-3 регулярна граматика | S → ε A → aB (праволінійна) або A → Ba (ліволінійна) A → a A → ε A, B ∈ N, a ∈ Σ | регулярна | Скінченний автомат (як детермінований, так і недетермінований) | А |
Позначення множин
- Σ: множина термінальних символів
- N: множина нетермінальних символів
- V=Σ ∪ N: словник граматики (множина всіх термінальних та нетермінальних символів)
Операції
- C = Доповнення множин
- K =
- S = Перетин множин
- V = Об'єднання множин
- * = Зірочка Кліні
Ієрархія
Граматика типу 0
Визначення
Граматики типу 0 називають необмеженими. До них належать всі формальні граматики виду G = (Σ, N, S, P), де Σ — це скінченний алфавіт, N — множину нетермінальних символів, S ∈ N — початковий символ, а P — множину правил виведення P: ((Σ ∪ N)* N(Σ ∪ N)*)) × (Σ ∪ N)*.
Записують G ∈ Тип0.
Мови породжені граматиками типу 0
Кожна граматика типу 0 породжує мову, яку може розпізнати машина Тюринга, та навпаки: для кожної мови, яку може розпізнати машина Тюринга, існує граматика типу 0, яка здатна її породити. Такі мови також відомі, як .
Слід, однак, відрізняти цю множину мов від множини .
Граматики типу 1
Визначення
Граматики типу 1 ще називають контекстно-залежними. До них належать всі граматики типу 0, в яких правила виводу обмежено правилами вигляду α A β → α γ β або S → ε, де A — нетермінальний, а α, γ, β слова з термінальних (Σ) та нетермінальних (N) символів. Слова α und β можуть бути порожніми, але γ має містити щонайменше один символ (термінальний або нетермінальний).
Правило S → ε дозволене, якщо S не зустрічається в правій частині жодного з правил. Це правило необіхдне для додавання порожнього слова ε.
Якщо граматика G контекстно-вільна, записують G ∈ Тип1.
На відміну від контекстно-незалежних граматик, кількість символів у лівій частині правила може бути > 1.
Мови породжені граматиками типу 1
Контекстно-залежні (КЗ) граматики породжують ; тобто, кожна КЗ-граматика породжує КЗ-мову, і навпаки — для кожної КЗ мови існує КЗ граматика, що її породжує.
Контекстно-залежні мови можна розпізнати недетермінованою ; тобто, недетермінованою машиною Тюринга, довжина стрічки якої обмежена.
Монотонні граматики
Якщо за винятком правила S → ε в правилі α → β довжина α не більша за довжину β, |α| ≤ |β| то таку КЗ-граматику називають монотонною.
Монотонні граматики також породжують КЗ-мови, однак не кожна монотонна граматика контекстно-залежна.
Граматики типу 2 (контекстно-вільні)
Визначення
Граматики типу 2 також називають контекстно-вільними (КВ).
В кожному правилі граматики другого типу з лівої сторони знаходиться один нетермінальний символ, а з правої сторони — можливо порожня послідовність термінальних та нетермінальних символів. Тобто, правила виводу обмежені:
Граматики типу 2 мають лише правила виду A → γ, A — нетермінальний символ, а γ складається з послідовності тремінальних та нетермінальних символів.
Записують G ∈ Тип2.
Мови породжені граматиками типу 2
Контекстно-вільні (КВ) граматики породжують КВ-мови, і для кожної КВ-мови існує КВ-граматика, що її породжує.
Контекстно-вільні мови розпізнаються недетермінованими . КВ-мови відіграють важливу роль в теорії та побудові синтаксису мов програмування.
Граматики типу 3 (право- та ліво- лінійні граматики)
Визначення
Граматики третього типу називають регулярними. До них належать граматики другого типу, правила виводу яких обмежено . Тобто, в лівій частині правила виводу зхнаходиться один нетермінальний символ. В правій частині праволінійні граматики мають один термінальний за ним, можливо, один нетермінальний. Так звані ліволінійні граматики мають в правій частині правила один нетермінальний символ, за яким, можливо, один термінальний.
Таким чином, граматики третього типу мають лише правила, в яких ліва частина складається з одного нетермінального символу, а права, з одного термінального слід за яким, можливо, йде термінальний (або навпаки, термінальний, за яким, можливо, нетермінальний).
Для кожної ліволінійної граматики існує праволінійна граматика, та навпаки, які генерують однакові мови.
Записують G ∈Тип3.
Мови породжені граматиками типу 3
Регулярні граматики породжують регулярні мови, і для кожної регулярної мови існує регулярна граматика, що її породжує.
Регулярні мови можна описувати також регулярними виразами. Регулярні мови можливо розпізнавати скінченними автоматами. Їх часто використовують для пошуку фрагментів тексту, або для визначення лексичної структури мови програмування.
Ієрархія Чомскі формальних мов
Формальна мова належить до типу i, якщо її породжує граматика типу i. Формально, мова L належить до типу i ∈ {0, …, 3} якщо існує граматика G ∈ Типi така, що L = L(G). Тоді пишуть
В ієрархії Чомскі, множина мов типу i є підмножиною мов типу i − 1. Кожна контекстно-залежна мова рекурсивно зліченна, але існують рекурсивно зліченні мови, які не є контекстно-залежними. Так само кожна контекстно-вільна мова є контекстно-залежною, але не навпаки, та кожна регулярна мова контекстно-вільна але не кожна контекстно-вільна мова регулярна.
Класи формальних мов мають відношення .
Серед прикладів мов різних класів можна назвати:
- Проблема зупинки належить до типу 0, але не до типу 1.
- належить до типу 1, але не 2.
- належить до типу 2, але не 3.
Природні мови
Хоча дослідження формальних граматик Чомскі збирався використати для створення математичного описання природної мови, досі вдалось розробити формальні граматики для декількох мов, в першу чергу, штучних. Проблема полягає, зокрема, в багатозначності слів природної мови. Правильне значення можна отримати шляхом аналізу розширеного контексту, в якому знаходиться аналізоване речення, або його значення взагалі неможливо встановити.
Див. також
Примітки
- . Архів оригіналу за 15 грудня 2010. Процитовано 26 березня 2010.
Література
- Noam Chomsky. [PDF ] — 1956. — Т. Vol.2. — С. 113–124. — (IRE Transactions on Information Theory) з джерела 19 вересня 2010
- Noam Chomsky. On certain formal properties of grammars. — 1959. — Т. Vol.2. — С. 137–167. — (Information and Control)
- Noam Chomsky, Marcel P. Schützenberger. The algebraic theory of context free languages, Computer Programming and Formal Languages / P. Braffort, D. Hirschberg. — Amsterdam, 1963. — С. 118–161.
- Sander, Stucky, Herschel. Automaten, Sprachen, Berechenbarkeit. — Stuttgart : Teubner, 1992. — .
Це незавершена стаття про мови програмування. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (березень 2010) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Iyera rhiya Cho mski abo Iyera rhiya Cho mski Shutcenbe rgera nazvana na chest movoznavcya Noama Chomski ta matematika ponyattya v teoretichnij informatici yakim poznachayut iyerarhiyu formalnih gramatik yaki porodzhuyut formalni movi Vpershe opisana Noamom Chomski v 1956 roci Chotiri opisani Chomski tipi gramatik vihodyat vid bazovoyi neobmezhenoyi gramatiki gramatika tipu 0 na yaku poslidovno nakladayut obmezhennya na pravila produkciyi V zalezhnosti vid tipu najprostishoyi gramatiki yaka mozhe zgeneruvati zadanu formalnu movu formalni movi dilyat na vidpovidni kategoriyi vid tipu 0 do tipu 3 VstupFormalni movi vidigrayut v informatici vazhlivu rol Zavdyaki nim informaciyu mozhna predstavlyati u viglyadi pridatnomu dlya avtomatichnogo analizu ta obrobki na komp yuteri Formalni movi v dechomu podibni do prirodnih Voni skladayutsya z mnozhini tak zvanih terminalnih simvoliv yim vidpovidayut skladi v prirodnih movah yaki mozhna skladati v slova Krim togo zadani pravila yih nazivayut gramatikoyu yaki vkazuyut sposobi pobudovi viraziv na osnovi sliv virazi analogichni rechennyam prirodnoyi movi Navedeni prikladi ne svidchat pro povnu identichnist a lishe vkazuyut na osnovnu ideyu ponyattya Sered prikladiv zastosuvannya formalnih mov mozhna nazvati movi programuvannya abo movi rozmitki danih napriklad XML abo HTML Slid zvernuti uvagu na te sho formalni movi viznachayut lishe sposib predstavlennya danih napriklad te sho XML dani pobudovani z vkladenih tegiv ale ne sami dani Ideya formalnih mov polyagaye v stvorenni tochnogo matematichnogo opisu dlya podibnih mov Na osnovi cogo opisu mozhna buduvati zasobi dlya avtomatichnoyi obrobki cih mov tak zvani sintaksichni analizatori V poperednomu abzaci vzhe nazvano osnovni skladovi formalnoyi movi Takozh slid dodati mnozhinu osnovnih simvoliv alfavit Alfavit zazvichaj poznachayut S displaystyle Sigma i mozhe skladatis napriklad zi zvichnih liter cifr tosho She odniyeyu skladovoyu formalnoyi movi ye gramatika Gramatiki zadayut pravilami pidstanovki vidu a b Za cim pravilom mozhna zaminiti dijsne slovo poznachene yak a na slovo poznachene yak b ta otrimati dijsne slovo movi Na dodachu zadayut pochatkovij simvol chasto yak aksiomu Pochatkovij simvol za viznachennyam ye slovom z movi Takozh slid vidriznyati ta neterminalni simvoli Strogo kazhuchi slova ta rechennya formalnoyi movi mozhut skladatis lishe z terminalnih simvoliv napriklad literi alfavitu Neterminalni simvoli takozh nazivayut zminnimi vidpovidayut pevnim chinom deyakomu ponyattyu V nastupnomu prikladi opisano movu yaka porodzhuye matematichni virazi sumi Terminalni simvoli pidkresleni a neterminalni vidileno kursivom Kozhen ryadok viznachaye odne pravilo Suma Cifra Suma Suma Cifra Suma Suma Cifra Cifra 1 9 Aksiomoyu v cij movi ye Suma Vihodyachi z neyi zastosuvannyam navedenih vishe pravil mozhna otrimati neobhidnij viraz Suma Aksioma Suma Cifra Zastosovano 3 pravilo Suma Cifra Cifra Zastosovano 2 pravilo Cifra Cifra Cifra Zastosovano 1 pravilo 1 Cifra Cifra Zastosovano 4 pravilo 1 2 Cifra Zastosovano 4 pravilo 1 2 9 Zastosovano 4 pravilo Poryadok zastosuvannya pravil dovilnij Gramatika viznachaye lishe pravila yaki dozvoleno vikoristovuvati u potochnij situaciyi i ne daye vkazivki yaki pravila mayut buti zastosovani Napriklad do pershogo rechennya mozhna zastosuvati pravila 1 3 ta ne mozhna zastosuvati 4 pravilo Pochinayuchi z 4 rechennya mozhlive zastosuvannya lishe 4 pravila Formalni gramatiki dozvolyayut opisuvati skladnishi formalni movi Napriklad sintaksis movi programuvannya Paskal viznacheno u viglyadi formalnoyi gramatiki Iyerarhiya Chomski namagayetsya klasifikuvati neobmezheni v principi movi simvolni virazi ta pravila Dlya cogo zaprovadzhuyut pevni klasi mov dlya yakih mozhlivo vstanoviti shvidkodiyu ta pidhid do komp yuternoyi obrobki Krim togo movi tim bilshe obmezheni chim glibshe znahodyatsya v iyerarhiyi Vzagali mozhna pomititi sho prostishi movi z odnogo boku prostishe piddayutsya komp yuternij obrobci a z inshogo yim brakuye viraznosti Napriklad dlya poshuku deyakih shabloniv u teksti vikoristovuyut regulyarni virazi Regulyarni virazi vidpovidayut gramatikam Chomski tipu 3 Prosto yihnoyi viraznosti dosit abi shukati riznomanitni fragmenti tekstu ale yih ne dostatno dlya napriklad opisannya mov programuvannya Dlya opisannya mov programuvannya vikoristovuyut zazvichaj gramatiki tipu 2 OglyadDali poznachatimemo formalnu gramatiku G N S P S Tak N oznachatime mnozhinu neterminalnih simvoliv S mnozhinu terminalnih simvoliv P mnozhinu pravil vivodu ta S pochatkovij simvol V nastupnij tablici navedeno oglyad chotiroh tipiv formalnih gramatik pravil vivodu formalnih mov ta avtomati zdatni yih rozpiznati Gramatika Pravila Movi Avtomati Skorochennya Tip 0 Dovilna formalna gramatika a b a V N V b V Mashina Tyuringa KSV Tip 1 Kontekstno zalezhna gramatika a A b a g b A N a b V g V S e dozvolene koli sered pravil P vidsutnye a b Sg KZ Tip 2 Kontekstno vilna gramatika A g A N g V kontekstno vilna nedeterminovanij avtomat z magazinnoyu pam yatyu KV Tip 3 regulyarna gramatika S e A aB pravolinijna abo A Ba livolinijna A a A e A B N a S regulyarna Skinchennij avtomat yak determinovanij tak i nedeterminovanij A Poznachennya mnozhin S mnozhina terminalnih simvoliv N mnozhina neterminalnih simvoliv V S N slovnik gramatiki mnozhina vsih terminalnih ta neterminalnih simvoliv Operaciyi C Dopovnennya mnozhin K S Peretin mnozhin V Ob yednannya mnozhin Zirochka KliniIyerarhiyaGramatika tipu 0 Dokladnishe Formalna gramatika Viznachennya Gramatiki tipu 0 nazivayut neobmezhenimi Do nih nalezhat vsi formalni gramatiki vidu G S N S P de S ce skinchennij alfavit N mnozhinu neterminalnih simvoliv S N pochatkovij simvol a P mnozhinu pravil vivedennya P S N N S N S N Zapisuyut G Tip0 Movi porodzheni gramatikami tipu 0 Kozhna gramatika tipu 0 porodzhuye movu yaku mozhe rozpiznati mashina Tyuringa ta navpaki dlya kozhnoyi movi yaku mozhe rozpiznati mashina Tyuringa isnuye gramatika tipu 0 yaka zdatna yiyi poroditi Taki movi takozh vidomi yak Slid odnak vidriznyati cyu mnozhinu mov vid mnozhini Gramatiki tipu 1 Dokladnishe Kontekstno zalezhna gramatika Viznachennya Gramatiki tipu 1 she nazivayut kontekstno zalezhnimi Do nih nalezhat vsi gramatiki tipu 0 v yakih pravila vivodu obmezheno pravilami viglyadu a A b a g b abo S e de A neterminalnij a a g b slova z terminalnih S ta neterminalnih N simvoliv Slova a und b mozhut buti porozhnimi ale g maye mistiti shonajmenshe odin simvol terminalnij abo neterminalnij Pravilo S e dozvolene yaksho S ne zustrichayetsya v pravij chastini zhodnogo z pravil Ce pravilo neobihdne dlya dodavannya porozhnogo slova e Yaksho gramatika G kontekstno vilna zapisuyut G Tip1 Na vidminu vid kontekstno nezalezhnih gramatik kilkist simvoliv u livij chastini pravila mozhe buti gt 1 Movi porodzheni gramatikami tipu 1 Kontekstno zalezhni KZ gramatiki porodzhuyut tobto kozhna KZ gramatika porodzhuye KZ movu i navpaki dlya kozhnoyi KZ movi isnuye KZ gramatika sho yiyi porodzhuye Kontekstno zalezhni movi mozhna rozpiznati nedeterminovanoyu tobto nedeterminovanoyu mashinoyu Tyuringa dovzhina strichki yakoyi obmezhena Monotonni gramatiki Yaksho za vinyatkom pravila S e v pravili a b dovzhina a ne bilsha za dovzhinu b a b to taku KZ gramatiku nazivayut monotonnoyu Monotonni gramatiki takozh porodzhuyut KZ movi odnak ne kozhna monotonna gramatika kontekstno zalezhna Gramatiki tipu 2 kontekstno vilni Dokladnishe Kontekstno vilna gramatika Viznachennya Gramatiki tipu 2 takozh nazivayut kontekstno vilnimi KV V kozhnomu pravili gramatiki drugogo tipu z livoyi storoni znahoditsya odin neterminalnij simvol a z pravoyi storoni mozhlivo porozhnya poslidovnist terminalnih ta neterminalnih simvoliv Tobto pravila vivodu obmezheni w 1 w 2 P w 1 N w 2 N S displaystyle forall w 1 rightarrow w 2 in P w 1 in N land left w 2 in N cup Sigma ast right Gramatiki tipu 2 mayut lishe pravila vidu A g A neterminalnij simvol a g skladayetsya z poslidovnosti treminalnih ta neterminalnih simvoliv Zapisuyut G Tip2 Movi porodzheni gramatikami tipu 2 Kontekstno vilni KV gramatiki porodzhuyut KV movi i dlya kozhnoyi KV movi isnuye KV gramatika sho yiyi porodzhuye Kontekstno vilni movi rozpiznayutsya nedeterminovanimi KV movi vidigrayut vazhlivu rol v teoriyi ta pobudovi sintaksisu mov programuvannya Div takozh Notaciya Bekusa Naura Gramatiki tipu 3 pravo ta livo linijni gramatiki Dokladnishe Regulyarna gramatika Viznachennya Gramatiki tretogo tipu nazivayut regulyarnimi Do nih nalezhat gramatiki drugogo tipu pravila vivodu yakih obmezheno w 1 w 2 P w 1 N displaystyle forall w 1 rightarrow w 2 in P w 1 in N land w 2 S S N N S e displaystyle w 2 in Sigma cup Sigma cdot N dot lor N cdot Sigma cup varepsilon Tobto v livij chastini pravila vivodu zhnahoditsya odin neterminalnij simvol V pravij chastini pravolinijni gramatiki mayut odin terminalnij za nim mozhlivo odin neterminalnij Tak zvani livolinijni gramatiki mayut v pravij chastini pravila odin neterminalnij simvol za yakim mozhlivo odin terminalnij Takim chinom gramatiki tretogo tipu mayut lishe pravila v yakih liva chastina skladayetsya z odnogo neterminalnogo simvolu a prava z odnogo terminalnogo slid za yakim mozhlivo jde terminalnij abo navpaki terminalnij za yakim mozhlivo neterminalnij Dlya kozhnoyi livolinijnoyi gramatiki isnuye pravolinijna gramatika ta navpaki yaki generuyut odnakovi movi Zapisuyut G Tip3 Movi porodzheni gramatikami tipu 3 Regulyarni gramatiki porodzhuyut regulyarni movi i dlya kozhnoyi regulyarnoyi movi isnuye regulyarna gramatika sho yiyi porodzhuye Regulyarni movi mozhna opisuvati takozh regulyarnimi virazami Regulyarni movi mozhlivo rozpiznavati skinchennimi avtomatami Yih chasto vikoristovuyut dlya poshuku fragmentiv tekstu abo dlya viznachennya leksichnoyi strukturi movi programuvannya Iyerarhiya Chomski formalnih movFormalna mova nalezhit do tipu i yaksho yiyi porodzhuye gramatika tipu i Formalno mova L nalezhit do tipu i 0 3 yaksho isnuye gramatika G Tipi taka sho L L G Todi pishut L L i displaystyle L in mathcal L i V iyerarhiyi Chomski mnozhina mov tipu i ye pidmnozhinoyu mov tipu i 1 Kozhna kontekstno zalezhna mova rekursivno zlichenna ale isnuyut rekursivno zlichenni movi yaki ne ye kontekstno zalezhnimi Tak samo kozhna kontekstno vilna mova ye kontekstno zalezhnoyu ale ne navpaki ta kozhna regulyarna mova kontekstno vilna ale ne kozhna kontekstno vilna mova regulyarna Klasi formalnih mov mayut vidnoshennya L 3 L 2 L 1 L 0 displaystyle mathcal L 3 subset mathcal L 2 subset mathcal L 1 subset mathcal L 0 Sered prikladiv mov riznih klasiv mozhna nazvati Problema zupinki nalezhit do tipu 0 ale ne do tipu 1 L 1 a n b n c n n 1 displaystyle L 1 left a n b n c n n geq 1 right nalezhit do tipu 1 ale ne 2 L 2 a n b n n 1 displaystyle L 2 left a n b n n geq 1 right nalezhit do tipu 2 ale ne 3 Prirodni moviHocha doslidzhennya formalnih gramatik Chomski zbiravsya vikoristati dlya stvorennya matematichnogo opisannya prirodnoyi movi dosi vdalos rozrobiti formalni gramatiki dlya dekilkoh mov v pershu chergu shtuchnih Problema polyagaye zokrema v bagatoznachnosti sliv prirodnoyi movi Pravilne znachennya mozhna otrimati shlyahom analizu rozshirenogo kontekstu v yakomu znahoditsya analizovane rechennya abo jogo znachennya vzagali nemozhlivo vstanoviti Div takozhGramatika zalezhnostej Matematichna lingvistika Sintaksichnij analizPrimitki Arhiv originalu za 15 grudnya 2010 Procitovano 26 bereznya 2010 LiteraturaNoam Chomsky PDF 1956 T Vol 2 S 113 124 IRE Transactions on Information Theory z dzherela 19 veresnya 2010 Noam Chomsky On certain formal properties of grammars 1959 T Vol 2 S 137 167 Information and Control Noam Chomsky Marcel P Schutzenberger The algebraic theory of context free languages Computer Programming and Formal Languages P Braffort D Hirschberg Amsterdam 1963 S 118 161 Sander Stucky Herschel Automaten Sprachen Berechenbarkeit Stuttgart Teubner 1992 ISBN 3 519 02937 5 Ce nezavershena stattya pro movi programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2010