www.wikidata.uk-ua.nina.az

Контекстно залежна граматика скорочено КЗ граматика формальна граматика типу 1 в ієрархії Чомскі Особливість КЗ граматик

Контекстно-залежна граматика

Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 1 в ієрархії Чомскі. Особливість КЗ граматик в тому, що правила виводу здійснюють заміну нетермільнального символу лише у визначеному контексті.

Визначення Редагувати

Контекстно-залежна граматика, це формальна граматика де

  •  — множина нетермінальних символів
  •  — множина термінальних символів
  •  — початковий символ
  •  — правила виводу виду або , за умов:
    • відсутнє в правій частині правил виводу

Властивості Редагувати

За єдиним винятком, визначені правила виводу мають вид та .

Це означає, що нетермінальний символ в контексті та буде замінено на . Але, в той час, як довжина має бути не менше за одиницю, і і можуть бути порожніми.

Наступні приклади крайніх випадків відповідають визначенню:

Аби зробити можливим роботу з порожнім словом, дозволяють правило , за умови відсутності в правій частині правил виводу.

Контекстно-залежні та монотонні граматики Редагувати

Правила виводу КЗ-граматики не скорочують рядок в лівій частині. За винятком правила для правил виконується нерівність . Таким чином, КЗ-граматика завжди монотонна. КЗ- та монотонні граматики породжують однаковий клас мов.

Деякі автори наводять визначення КЗ-граматик в контексті монотонних. Правила виводу виду розглядають як типову або канонічну форму правил КЗ-граматик.

Нормальні форми Редагувати

Кожній КЗ-граматиці відповідає граматика в нормальній формі Куроди з правилами виводу виду:

Граматика в нормальній формі Куроди монотонна, але не завжди контекстно-залежна.

КЗ нормальна форма подовжуюча, якщо має правила виду:

Кожній КЗ граматиці відповідає подовжувальна граматика в нормальній формі.

Альтернативне позначення Редагувати

Мовознавці використовують інші позначення для правил виводу.. Правила підставляння визначають аналогічно правилам виводу, а в правій частині вказують контекст, в якому можна застосувати правило:

Мови породжені КЗ-граматиками Редагувати

Контекстно-залежні граматики породжують контекстно-залежні мови. Тобто, кожна КЗ граматика породжує КЗ мову, і для кожної КЗ мови існує КЗ граматика, що її породжує.

Контекстно-залежні мови можна розпізнати недетермінованою лінійно-обмеженою машиною Тюринга (недетермінована машина Тюринга зі стрічкою обмеженої довжини).

Визначення приналежності слва мові () для КЗ-мов розв'язувана.

Приклад Редагувати

Контекстно-залежну мову слів, які складаються з однакової кількості літер a за якими йдуть b та c, визначають наступною КЗ граматикою:

з термінальними символами та нетермінальними та правилами виводу

Слово можна отримати таким чином (підкреслено контекст, в якому відбувається заміна):

Див. також Редагувати

Примітки Редагувати

  1. наприклад Uwe Schöning. Abschnitt 1.1.2 // Theoretische Informatik – kurz gefasst. — 5. — Spektrum Akademischer Verlag, 2008. — ISBN 9783827418241.
  2. Klaus W. Wagner. Kapitel 6 // Theoretische Informatik: Eine kompakte Einführung. — Springer, 2003. — ISBN 9783540013136.
  3. див Rozenberg та Salomaa, Handbook of Formal Languages, S.190
  4. Daniel Jurafsky, James H. Martin. Частина 16 // Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. — Prentice Hall, 2009. — ISBN 9780131873216.
  5. J. C. Martin. Introduction to Languages and the Theory of Computation. — 3. — McGraw-Hill, 2002.

Література Редагувати

  • Grzegorz Rozenberg, Arto Salomaa. Handbook of Formal Languages: Word, Language, Grammar. — Springer, 1997. — Т. Vol.1. — ISBN 9783540604204.
  • Katrin Erk, Lutz Priese. Theoretische Informatik: Eine umfassende Einführung. — Springer, 2008. — ISBN 9783540763192.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Kontekstno zalezhna gramatika skorocheno KZ gramatika formalna gramatika tipu 1 v iyerarhiyi Chomski Osoblivist KZ gramatik v tomu sho pravila vivodu zdijsnyuyut zaminu netermilnalnogo simvolu lishe u viznachenomu konteksti Zmist 1 Viznachennya 1 1 Vlastivosti 1 2 Kontekstno zalezhni ta monotonni gramatiki 1 3 Normalni formi 1 4 Alternativne poznachennya 2 Movi porodzheni KZ gramatikami 3 Priklad 4 Div takozh 5 Primitki 6 LiteraturaViznachennya RedaguvatiKontekstno zalezhna gramatika ce formalna gramatika G N T P S displaystyle G N T P S nbsp de N displaystyle N nbsp mnozhina neterminalnih simvoliv T displaystyle T nbsp mnozhina terminalnih simvoliv S N displaystyle S in N nbsp pochatkovij simvol P displaystyle P nbsp pravila vivodu vidu a X b a g b displaystyle alpha X beta rightarrow alpha gamma beta nbsp abo S e displaystyle S rightarrow varepsilon nbsp za umov a b N T displaystyle alpha beta in N cup T nbsp X N displaystyle X in N nbsp g N T displaystyle gamma in N cup T nbsp S displaystyle S nbsp vidsutnye v pravij chastini pravil vivoduVlastivosti Redaguvati Za yedinim vinyatkom viznacheni pravila vivodu mayut vid a X b a g b displaystyle alpha X beta rightarrow alpha gamma beta nbsp ta g e displaystyle gamma neq varepsilon nbsp Ce oznachaye sho neterminalnij simvol X displaystyle X nbsp v konteksti a displaystyle alpha nbsp ta b displaystyle beta nbsp bude zamineno na g displaystyle gamma nbsp Ale v toj chas yak dovzhina g displaystyle gamma nbsp maye buti ne menshe za odinicyu i a displaystyle alpha nbsp i b displaystyle beta nbsp mozhut buti porozhnimi Nastupni prikladi krajnih vipadkiv vidpovidayut viznachennyu a X a g displaystyle alpha X rightarrow alpha gamma nbsp X b g b displaystyle X beta rightarrow gamma beta nbsp X g displaystyle X rightarrow gamma nbsp Abi zrobiti mozhlivim robotu z porozhnim slovom dozvolyayut pravilo S e displaystyle S rightarrow varepsilon nbsp za umovi vidsutnosti S displaystyle S nbsp v pravij chastini pravil vivodu Kontekstno zalezhni ta monotonni gramatiki Redaguvati Pravila vivodu KZ gramatiki ne skorochuyut ryadok v livij chastini Za vinyatkom pravila S e displaystyle S rightarrow varepsilon nbsp dlya pravil w 1 w 2 displaystyle w 1 rightarrow w 2 nbsp vikonuyetsya nerivnist w 1 w 2 displaystyle left w 1 right leq left w 2 right nbsp Takim chinom KZ gramatika zavzhdi monotonna KZ ta monotonni gramatiki porodzhuyut odnakovij klas mov Deyaki avtori navodyat viznachennya KZ gramatik v konteksti monotonnih 1 Pravila vivodu vidu a X b a g b displaystyle alpha X beta rightarrow alpha gamma beta nbsp rozglyadayut yak tipovu abo kanonichnu formu pravil KZ gramatik 2 Normalni formi Redaguvati Kozhnij KZ gramatici vidpovidaye gramatika v normalnij formi Kurodi z pravilami vivodu vidu A a displaystyle A rightarrow a nbsp A B displaystyle A rightarrow B nbsp A B C displaystyle A rightarrow BC nbsp A B C D displaystyle AB rightarrow CD nbsp Gramatika v normalnij formi Kurodi monotonna ale ne zavzhdi kontekstno zalezhna KZ normalna forma podovzhuyucha yaksho maye pravila vidu A a displaystyle A rightarrow a nbsp A B C displaystyle A rightarrow BC nbsp A B A C displaystyle AB rightarrow AC nbsp Kozhnij KZ gramatici vidpovidaye podovzhuvalna gramatika v normalnij formi 3 Alternativne poznachennya Redaguvati Movoznavci vikoristovuyut inshi poznachennya dlya pravil vivodu 4 Pravila pidstavlyannya viznachayut analogichno pravilam vivodu a v pravij chastini vkazuyut kontekst v yakomu mozhna zastosuvati pravilo X g a b displaystyle X rightarrow gamma alpha beta nbsp Movi porodzheni KZ gramatikami RedaguvatiKontekstno zalezhni gramatiki porodzhuyut kontekstno zalezhni movi Tobto kozhna KZ gramatika porodzhuye KZ movu i dlya kozhnoyi KZ movi isnuye KZ gramatika sho yiyi porodzhuye Kontekstno zalezhni movi mozhna rozpiznati nedeterminovanoyu linijno obmezhenoyu mashinoyu Tyuringa nedeterminovana mashina Tyuringa zi strichkoyu obmezhenoyi dovzhini Viznachennya prinalezhnosti slva movi x L displaystyle x in L nbsp dlya KZ mov rozv yazuvana Priklad RedaguvatiKontekstno zalezhnu movu L a n b n c n n 1 displaystyle L a n b n c n n geq 1 nbsp sliv yaki skladayutsya z odnakovoyi kilkosti liter a za yakimi jdut b ta c viznachayut nastupnoyu KZ gramatikoyu 5 G N T P S displaystyle G N T P S nbsp z terminalnimi simvolami T a b c displaystyle T a b c nbsp ta neterminalnimi N B C H S displaystyle N B C H S nbsp ta pravilami vivodu P displaystyle P nbsp S a S B C a B C displaystyle S rightarrow aSBC mid aBC nbsp C B H B displaystyle CB rightarrow HB nbsp H B H C displaystyle HB rightarrow HC nbsp H C B C displaystyle HC rightarrow BC nbsp a B a b displaystyle aB rightarrow ab nbsp b B b b displaystyle bB rightarrow bb nbsp b C b c displaystyle bC rightarrow bc nbsp c C c c displaystyle cC rightarrow cc nbsp Slovo a a b b c c L displaystyle aabbcc in L nbsp mozhna otrimati takim chinom pidkresleno kontekst v yakomu vidbuvayetsya zamina S 1 a S B C 1 a a B C B C 2 a a B H B C 3 a a B H C C 4 a a B B C C 5 a a b B C C 6 a a b b C C 7 a a b b c C 8 a a b b c c displaystyle begin array l underline S Rightarrow 1 a underline S BC Rightarrow 1 aaB underline CB C Rightarrow 2 aaB underline HB C Rightarrow 3 aaB underline HC C Rightarrow 4 a underline aB BCC Rightarrow 5 aa underline bB CC Rightarrow 6 aab underline bC C Rightarrow 7 aabb underline cC Rightarrow 8 aabbcc end array nbsp Div takozh RedaguvatiGramatika zalezhnostejPrimitki Redaguvati napriklad Uwe Schoning Abschnitt 1 1 2 Theoretische Informatik kurz gefasst 5 Spektrum Akademischer Verlag 2008 ISBN 9783827418241 Klaus W Wagner Kapitel 6 Theoretische Informatik Eine kompakte Einfuhrung Springer 2003 ISBN 9783540013136 div Rozenberg ta Salomaa Handbook of Formal Languages S 190 Daniel Jurafsky James H Martin Chastina 16 Speech and Language Processing An Introduction to Natural Language Processing Computational Linguistics and Speech Recognition Prentice Hall 2009 ISBN 9780131873216 J C Martin Introduction to Languages and the Theory of Computation 3 McGraw Hill 2002 Literatura Redaguvati nbsp Portal Matematika Grzegorz Rozenberg Arto Salomaa Handbook of Formal Languages Word Language Grammar Springer 1997 T Vol 1 ISBN 9783540604204 Katrin Erk Lutz Priese Theoretische Informatik Eine umfassende Einfuhrung Springer 2008 ISBN 9783540763192 Otrimano z https uk wikipedia org w index php title Kontekstno zalezhna gramatika amp oldid 31583395