Класификация на граматиките и езиците - MathHelpPlanet
Обсъждане и решаване на задачи по математика, физика, химия, икономика
Часова зона: UTC + 3 часа [DST]
Въведение в анализа
Теория на опашката (QS)
Класификация на граматиките и езиците
Спомнете си, че единственото ограничение, наложено върху правилото за извод на всяка граматика, е, че лявата страна на правилото трябва да съдържа поне един нетерминал. В зависимост от допълнителните ограничения, наложени на правилата за граматически извод, се разграничават следните основни класове граматики.
1. Тип 0 граматики или общи граматики. Тук не се налагат допълнителни ограничения върху правилата за извод.
2. Несъкращаващи се граматики. Всяко правило на такава граматика има формата [math]\alpha\to\beta[/math] , където [math]\alpha\leqslant\beta[/math] . По този начин дължината на дясната страна на правилото не е по-малка от дължината на лявата страна. Граматиката [math]G_4[/math] от пример 7.5 е граматика без съкращаване, но граматиката [math]G_5[/math] от същия пример не е.
3. Контекстно-зависими граматики (KZ-граматики). Една граматика се нарича контекстно-чувствителна граматика (KZ-граматика), ако някое от нейните правила за извод има формата [math]\varphi A\psi\to\varphi\xi\psi[/math] , където [math]A[/math] е нетерминал, [math]\xi[/math] е някакъв низ, [math]\xi\ne\lambda[/math] . Всяко такова правило, наречено Q3-правило, позволява да се замени нетерминалният [math]A[/math] в "контекста", образуван от низовете [math]\varphi[/math] и [math]\psi[/math] в комбинираната азбука с непразния низ [math]\xi[/math] (вижте Забележка 7.1). Понякога веригата [math]\varphi[/math] се нарича ляв контекст, а веригата [math]\psi[/math] се нарича десен контекст на дадено Q3-правило. От дефиницията е ясноче всяка K3-граматика е несъкращаваща се.
Граматиката [math]G_4[/math] в Пример 7.5 не е CG граматика, защото правилото [math]CB\to BC[/math] не е CG правило. Останалите правила за извод на тази граматика са правила за късо съединение. Граматиката [math]G_5[/math] от пример 7.5 не е CG граматика дори само поради наличието на правило за извод с празна дясна страна. K3-граматиката е граматиката от Пример 7.3.
Ако премахнем изискването веригата [math]\xi[/math] да не е празна в Q3-правилото, тогава получаваме граматика, която се нарича обобщена Q3-граматика (или накратко OKZ-граматика).
4. Безконтекстни граматики (CS-граматики). Всяко правило на такава граматика има формата [math]A\to\alpha[/math] , т.е. лявата страна на всяко правило за извод е нетерминал, а дясната страна е произволен (може би празен) низ в комбинираната азбука.
От практическа гледна точка това е най-важният клас граматики, тъй като синтаксисът на езиците за програмиране е описан от гледна точка на CF-граматики и отделна глава ще бъде посветена на тези граматики. Граматиките [math]G_2,G_3,G_4[/math] от Пример 7.5 са COP граматики.
5. Линейни граматики. Всяко правило на такава граматика има формата [math]A\to uBv[/math] или [math]A\to u[/math] , т.е. дясната страна на правило може да съдържа не повече от едно срещане на нетерминал. Ако всички правила от формата [math]A\to uBv[/math] съдържат [math]v=\lambda[/math] , тогава граматиката се нарича дяснолинейна, а ако [math]u=\lambda[/math] - ляволинейна.
Пример 7.6. Граматиката [math]G_6=(\, \,S, P_6)[/math] е линейна, където наборът от правила за извод [math]P_6[/math] е
Може да се докаже, че тази граматика генерира всички палиндроми в азбуката [math]V[/math] , т.е. всички вериги прочетеникакто от ляво на дясно, така и от дясно на ляво. Например, за [math]V=\[/math] низът [math]acbbca[/math] е палиндром. Неговият изход в граматиката [math]G_6[/math] (за дадената терминална азбука) ще изглежда така
Забележка 7.2. Формалната дефиниция на палиндром е следната. Наричаме обръщане на непразна верига
За празен низ [math]\lambda[/math] по дефиниция приемаме [math]\lambda^R= \lambda[/math] . Палиндром в азбуката [math]V[/math] е всеки низ [math]x[/math], за който [math]x^R=x[/math] .
6. Редовни граматики. В такава граматика всяко правило е във формата [math]A\to aB[/math] или [math]A\to a[/math] , където [math]a[/math] е или терминал, или празен низ. Редовните граматики са специален случай на дяснолинейни граматики.
Тези граматики ще бъдат обсъдени подробно в следващата лекция.
Твърдения за класове граматики
Нека представим, без доказателства, някои твърдения за класове граматики.
Теорема 7.2. 1. За всяка граматика от тип 0 може да се конструира еквивалентна GCZ граматика.
2. За всяка несъкращаваща се граматика може да се конструира K3-граматика, еквивалентна на нея.
3. За всяка ляволинейна граматика може да се конструира еквивалентна на нея дяснолинейна граматика и, обратно, за всяка дяснолинейна граматика може да се построи ляволинейна граматика, еквивалентна на нея.
4. За всяка дяснолинейна граматика може да се конструира еквивалентна на нея регулярна граматика.
Имайте предвид, че доказателствата на първите две точки от теорема 7.2 са доста нетривиални.
Класификацията на езиците, генерирани от граматики, е тясно свързана с класификацията на самите граматики, въпреки че не е идентична с нея. Един език принадлежи към клас [math]C[/math], ако съществува граматика от клас [math]C[/math],генериране на този език. По този начин са дефинирани езици от тип 0, езици без съкращаване, контекстно-зависими езици (KZ-езици), обобщени контекстно-зависими езици (GKZ-езици), контекстно-свободни езици (CF-езици), линейни езици, дясно- и ляво-линейни езици, редовни езици.
Тъй като всяка IBZ граматика е граматика от тип 0, тогава, в съответствие с точка 1 от теорема 7.2, класовете езици от тип O и IBZ езици съвпадат. По силата на т. 2 на същото твърдение, а също и с оглед на факта, че всяка KZ-граматика е несъкращаваща се граматика, класовете на несъкращаващи се и KZ-езици съвпадат. По силата на т. 3 и 4 от теорема 7.2 класовете дяснолинейни, ляволинейни и регулярни езици съвпадат.
Но следните факти могат да бъдат доказани.
Теорема 7.3. 1. Има CGT език, който не е CG език.
2. Има K3-език, който не е KZ-език.
3. Има CS-език, който не е линеен език.
4. Има линеен език, който не е нормален език.
Някои от твърденията на теорема 7.3 ще бъдат доказани по-късно. Засега отбелязваме само, че езиците, генерирани от граматиките [math]G_4[/math] и [math]G_5[/math] от Пример 7.5, не са COP езици, въпреки че за езика, генериран от граматиката [math]G_5[/math], може да се конструира C3 граматика, която го генерира. Езикът на регулярните структури в скоби, генериран от граматиката [math]G_3[/math] в пример 7.5, не е линеен език, а езикът на палиндромите в пример 7.6 не е нормален език.
Така че може да се твърди, че се извършват следните стриктни включвания на класове езици:
където REG, LIN, KS, KZ, OKZ, TYPE 0 са класове съответно редовни, линейни, KS-езици, KZ-езици, OKZ-езици и езици от тип 0.
Забележка 7.3. По силата на т. 1 от теорема 7.3, изискването, че в K3-правилото[math]\varphi A\psi\to\varphi\xi\psi[/math] веригата [math]\xi[/math] не е празна, е фундаментална. В една от следващите лекции ще докажем, че с известни резерви класът CF-езици може да бъде включен в класа CV-езици, тъй като всяка CF-граматика може да бъде преобразувана в еквивалентна CF-граматика, която не съдържа правило за извод от формата [math]A\to\lambda[/math] .
Основната разлика между класификацията на граматиките и езиците е следната. За да се определи класът на една граматика, е достатъчно да се разгледа нейният набор от правила за извод. За да се докаже "положително" твърдение, че даден език е език от такъв и такъв клас, е достатъчно да се измисли произволна граматика от съответния клас, който го генерира. Но за да се докаже "отрицателното" твърдение за класа на езика, т.е. за да се докаже, че даден език не принадлежи към такъв и такъв клас езици, трябва да се докаже, че няма граматика на съответния клас, която да го генерира. Тази задача е много по-трудна. Някои методи за конструиране на такива доказателства ще бъдат обсъдени по-долу.