Лекция 7 Formal gramatika



Download 2,49 Mb.
bet2/5
Sana09.12.2022
Hajmi2,49 Mb.
#882709
TuriЛекция
1   2   3   4   5
Bog'liq
7- Лекция. Формал грамматика

Формал грамматика

Определение формальной грамматики и языка


Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.
Определение 1.9. Формальной грамматикой называется четверка вида:







Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
Контекстно-свободная грамматика (КС-грамматикабесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала (в отличие от общего случая неограниченной грамматики Хомского).
Контекстно-зависимая грамматика ( CSG ) является формальной грамматикой , в которой левые стороны и правые стороны каких - либо правила производства могут быть окружены контекстом терминальных и нетерминальных символов . Контекстно-зависимые грамматики являются более общими, чем контекстно-свободные , в том смысле, что есть языки, которые могут быть описаны с помощью CSG, но не контекстно-свободных грамматик. Контекстно-зависимые грамматики менее общие (в том же смысле), чем неограниченные грамматики . Таким образом, CSG расположены между контекстно-свободной и неограниченной грамматиками в иерархии Хомского .
Хомский ввел контекстно-зависимые грамматики как способ описания синтаксиса естественного языка, когда часто бывает, что слово может или не может быть подходящим в определенном месте в зависимости от контекста. Уолтер Савич раскритиковал терминологию «контекстно-зависимая» как вводящую в заблуждение и предложил «не стирать» как лучшее объяснение различия между CSG и неограниченной грамматикой .
К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками (англ. unrestricted grammars), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны машиной Тьюринга. Эти языки также известны как рекурсивно перечислимые (англ. recursively enumerable).
Правила можно записать в виде:
α→βα→β, где αα — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а ββ — любая цепочка символов из алфавита.

Download 2,49 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish