Четени през летния семестър на учебната 2002/2003 година. Лектор тогава беше професор Димитър Скордев. Използвал съм мои (и на мои колеги) записки от лекции, както и материалите на проф. Скордев на http://www.fmi.uni-sofia.bg/fmi/logic/skordev/ln/. Префиксни изрази над множество от думи
нека е дадена азбука A;
дължина на думата A* ще означаваме с ||;
в азбуката A част от символите са отделени от другите и имат спомагателна роля:
-
леви ограничители;
-
десни ограничители;
-
разделители;
трите множества са чужди помежду си;
например в термините на езика PROLOG можем да си мислим, че A е съставена от всички малки и големи латински букви, десетичните цифри, подчертаване - _, кръглите скоби - (, ),
запетая - ,, двоеточие - :, точка и запетая - ;; единствен лявограничител е лявата скоба, единствен десен ограничител е дясната скоба, разделители са запетаята, двоеточието и точката със запетая;
нека е дадено множество A*, т.е. е множество от думи над азбуката A; част от думите над A ще наречем префиксни изрази над ; дефинираме префиксен израз над индуктивно:
База: всяка дума от е префиксен израз над ;
Предположение: нека w , E1, E2, …, En (n 1) са префиксни изрази над , l A е ляв ограничител, r A е десен ограничител и
s1 A, s2 A, …, sn-1 A са разделители;
Стъпка: тогава думата wlE1s1E2s2…En-1sn-1Enr е префиксен израз над ; (многоточието значи изброяване, то не е дума над A);
Заключение: няма други префиксни изрази над ;
в конкретния пример за езика PROLOG, думата от индукционната стъпка има следния вид: w(E1,E2, …,En);
префиксните изрази от базата на индуктивната дефиниция наричаме прости, от стъпката наричаме съставни;
основен проблем е осигуряването на еднозначен синтактичен анализ на префиксните изрази; това означава, че трябва да са изпълнени следните две изисквания:
-
простите префиксни изрази трябва да са различни от съставните; например, ако = A* това изискване очевидно е нарушено;
-
съставните префиксни изрази трябва да се прочитат еднозначно, т.е. ако
wlE1s1E2s2…En-1sn-1Enr = wlE1s1E2s2…Ek-1sk-1Ekr, то
w = w, l = l, n = k, E1 = E1, E2 = E2 …, En = En, s1 = s1,
s2 = s2, …, sn-1 = sn-1; например, ако , е разделител в A, (, ) са съответно ляв и десен ограничител, w , ,, и , , то думата w(,,,,) не се прочита еднозначно;
едно просто достатъчно условие за еднозначен синтактичен анализ е в думите от да не участват леви и десни ограничители и разделители; в следващите разглеждания ще предполагаме, че това условие е изпълнено;
нека A*;
с ЛО () ще означаваме броят на левите ограничители във ;
с ДО () ще означаваме броят на десните ограничители във ;
Лема 1.: във всеки префиксен израз, броят на левите ограничители е равен на броя на десните ограничители;
Доказателство:
нека е префиксен израз;
провеждаме индукция по построението на ;
База: ако , то ЛО () = ДО () = 0, тъй като по предположение думите от не съдържат леви и десни ограничители;
Предположение: нека = wlE1s1E2s2…En-1sn-1Enr, където
нека w , E1, E2, …, En (n 1) са префиксни изрази над ,
l е ляв ограничител, r е десен ограничител, s1, s2, …, sn-1 са разделители и ЛО (Ei) = ДО (Ei) за i = 1, 2, …, n;
Стъпка: тогава ЛО () = ЛО (wlE1s1E2s2…En-1sn-1Enr) =
= ЛО (w) + ЛО (l) + ЛО (E1) + ЛО (s1) + … + ЛО (En-1) + ЛО (sn-1) +
+ ЛО (En) + ЛО (r) = 1 + ЛО (E1) + … + ЛО (En), тъй като множествата на левите ограничители, десните ограничители и разделителите са чужди помежду си и думите от не съдържат леви ограничители;
аналогично ДО () = ДО (wlE1s1E2s2…En-1sn-1Enr) =
= ДО (w) + ДО (l) + ДО (E1) + ДО (s1) + … + ДО (En-1) + ДО (sn-1) +
+ ДО (En) + ДО (r) = ДО (E1) + … + ДО (En) + 1;
от индукционното предположение получаваме, че
1 + ЛО (E1) + … + ЛО (En) = ДО (E1) + … + ДО (En) + 1 и тогава
ЛО () = ДО ();
казваме, че думата A* е начало на думата A*, ако съществува A*, така че = ; ако , казваме че е същинско начало на ;
Лема 2.: нека е префиксен израз над ; тогава или не съдържа разделители, или всяко начало на , което завършва с разделител съдържа повече леви ограничители, отколкото десни;
Доказателство:
индукция по построението на ;
База: ако , то по предположение не съдържа разделители и твърдението е изпълнено;
Предположение: нека = wlE1s1E2s2…En-1sn-1Enr и твърдението е изпълнено за префиксните изрази E1, E2, …, En;
Стъпка: ако n = 1 и E1 не съдържа разделители, то твърдението е изпълнено; нека съдържа поне един разделител и нека е произволно начало на , което завършва с разделител;
ако завършва в sk за някое k { 1, 2, …, n-1} (това може да се случи при n > 1), то ЛО () = ЛО (wlE1s1E2s2…Ek-1sk) =
= 1 + ЛО (E1) + … + ЛО (Ek-1) и ДО () = ДО (wlE1s1E2s2…Ek-1sk) =
= ДО (E1) + … + ДО (Ek-1);
от лема 1. ЛО (Ei) = ДО (Ei) за i = 1, 2, …, k-1, така че
ЛО () > ДО ();
ако завършва в разделител в Ek, k { 1, 2, …, n}, то
= wlE1s1E2s2…Ek-1sk-1k, където k е начало на Ek, което завършва с разделител; тогава ЛО () = ЛО (wlE1s1E2s2…Ek-1sk-1k) =
= 1 + ЛО (E1) + … + ЛО (Ek-1) + ЛО (k) и ДО () =
= ДО (wlE1s1E2s2…Ek-1sk-1k) = ДО (E1) + … + ДО (Ek-1) + ДО (k);
от лема 1. имаме ЛО (Ei) = ДО (Ei) за i = 1, 2, …, k-1 и от индукционното предположение имаме, че ЛО (k) > ДО (k);
така ЛО () > ДО ();
Лема 3: ако E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek, където
Ei, Ej са префиксни изрази, sm, sp са разделители, то
n = k, E1 = E1, …, En = En, s1 = s1, …, sn-1 = sn-1;
Доказателство: провеждаме индукция по числото n;
База: (n = 1) имаме E1 = E1s1E2s2…Ek-1sk-1Ek;
да допуснем, че k > 1; тогава E1s1 е начало на E1, което завършва с разделител и от лема 2. ЛО (E1s1) > ДО (E1s1)
ЛО (E1) > ДО (E1), което е противоречие с лема 1.;
така k = 1 и E1 = E1;
Предположение: нека твърдението е изпълнено за n-1 (n > 1);
Стъпка: ще покажем, че твърдението е изпълнено за n;
имаме E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek;
да допуснем, че k = 1; тогава E1s1E2s2…En-1sn-1En = E1 и аналогично на базата ще достигнем до противоречие; така k > 1;
ще покажем, че E1 = E1; тъй като E1 и E1 са начала на една и съща дума, достатъчно е да покажем, че |E1| = |E1|;
ако допуснем, че |E1| > |E1|, то E1s1 е начало на E1, което завършва с разделител (k > 1) и подобно на базата достигаме до противоречие;
ако допуснем, че |E1| < |E1|, то E1s1 е начало на E1, което завършва с разделител (n > 1) и подобно на базата достигаме до противоречие;
така |E1| = |E1| E1 = E1
s1E2s2…En-1sn-1En = s1E2s2…Ek-1sk-1Ek s1 = s1
E2s2…En-1sn-1En = E2s2…Ek-1sk-1Ek;
за получените думи прилагаме индукционното предположение; получаваме n – 1 = k – 1 n = k, E2 = E2, …, En = En, s2 = s2, …,
sn-1 = sn-1;
сега вече можем да покажем следната
Теорема: при направеното предположение е осигурен еднозначен синтактичен анализ на префиксните изрази;
Доказателство:
първото изискване очевидно е изпълнено, тъй като простите префиксни изрази не съдържат леви и десни ограничители;
нека wlE1s1E2s2…En-1sn-1Enr = wlE1s1E2s2…Ek-1sk-1Ekr;
първо ще покажем, че w = w; достатъчно е да покажем, че
|w| = |w|;
ако допуснем, че |w| > |w|, то wl е начало на w, което е противоречие, тъй като w не съдържа леви разделители;
ако допуснем, че |w| < |w|, то wl е начало на w, което е противоречие, тъй като w не съдържа леви разделители;
така |w| = |w| lE1s1E2s2…En-1sn-1Enr = lE1s1E2s2…Ek-1sk-1Ekr l = l E1s1E2s2…En-1sn-1Enr = E1s1E2s2…Ek-1sk-1Ekr r = r
E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek; от лема 3. получаваме n = k, E1 = E1, …, En = En, s1 = s1, …, sn-1 = sn-1;
Сподели с приятели: |