ПРЕФИКСНИ ИЗРАЗИ НАД ДАДЕНО МНОЖЕСТВО ОТ ДУМИ
Този въпрос играе подготвителна роля за описанието
на формален език, подходящ за нуждите на логическото програмиране.
Да предположим, че е дадена една азбука, съдържаща
измежду своите знаци двете кръгли скоби и запетаята. Тази азбука по-нататък ще я наричаме базисна. Когато по-нататък конкретни знаци от базисната азбука и думи над нея се срещат в текста в ролята именно на такива знаци и думи (а не като означения на нещо друго), за избягване на недоразумения ще ги изобразяваме с прав шрифт с фиксирана широчина на буквите (машинописен шрифт). За по-голяма отчетливост шрифтът ще бъде и получерен (дотук получерен машиношисен шрифт сме използвали в пример 3 от встъпителните бележки при изобразяване на конкретните букви от споменатата там трибуквена азбука и на конкретни думи над нея).
Пример 1. Нека освен скобите и запетаята базисната азбука съдържа още малките букви от латинската и от гръцката азбука и нека a е функцията, която преобразува всяка дума W над базисната азбука в по-дългата дума, получена от W чрез заграждането й в скоби. Тогава можем да напишем, че е в сила например равенството
a(baa) = (baa).
Тук скобите в дясната страна на равенството са употребени в ролята на знаци от базисната азбука, докато скобите в лявата страна изпълняват обичайната си роля в означение на прилагане на функция към аргумент (разбира се различни са и ролите на буквата a в началото на равенството и на буквите a по-нататък). Като разграничаваме току-що споменатите две роли на скобите, няма да имаме трудности и в тълкуването например на следните равенства:
a(a(W)) = a((W)) = ((W)).
Забележка 1. Има случаи, когато използването на различни шрифтове е невъзможно или затруднително. В такива случаи може да се използва един друг начин, а именно заграждане в кавички, за отбелязване на това, че на определено място дадеии знаци означават не нещо друго, а самите себе си. При използване на този начин равенствата от горния пример могат да се запишат по следния начин:
a("baa") = "(baa)",
a(a(W)) = a("("W")") = "(("W"))"
Ако W е едно множество от думи над базисната азбука, то някои думи над нея ще наричаме префиксни изрази над W. Дефиницията е индуктивна: така ще наричаме думите от W и всички думи от вида W(E1,E2...,En), където n е положително цяло число, W е дума от W и E1, E2, ..., En са префиксни изрази над W (при n=1 считаме, че думата ,E2...,En е празна, докато при n>1 тя очевидно не е празна). Префиксните изрази от втория вид ще наричаме съставни. Ще казваме, че префиксните изрази над W имат еднозначен анализ, ако никой съставен префиксен израз над W не принадлежи на самото W и всеки съставен префиксен израз има само едно представяне във въпросния втори вид. Съвсем лесно могат да се дадат примери, при които е нарушено първото от тези две условия. Сега ще дадем един пример, в който е нарушено второто от тях.
Пример 2. Нека множеството W съдържа като елементи еднобуквената дума с единствена буква запетая и двубуквената дума, състояща се от две запетаи. Тогава думата
,(,,,,) е префиксен израз над W с две различни представяния във вида W(E1,E2), където W е от W, а E1 и E2 са префиксни изрази над W: и при двете представяния W е запетая, но при едното представяне E1 и E2 се състоят съответно от една и от две запетаи, а при другото положението е обратното.
Едно достатъчно (но не необходимо) условие, за да имат префиксните изрази над W еднозначен анализ - това е условието в думите от W да не се срещат нито кръгли скоби, нито запетаи. За да се убедим в достатъчността на изказаното условие, да предположим, че то е изпълнено. Тогава поради наличието на kръгли скоби във всеки съставен префиксен израз над W
не е възможно такъв израз да принадлежи на самото W. Остава да покажем, че всеки съставен префиксен израз над W има само едно представяне във вида W(E1,E2...,En), където n е положително цяло число, W е дума от W и E1, E2, ..., En са префиксни изрази над W. Това може да се направи по следния начин. Първо с индукция, съобразена с дефиницията за префиксен израз над W, се доказва. че за всеки префиксен израз E над W са в сила следните две твърдения (доказателството е лесно и го оставяме за самостоятелно обмисляне):
1. В E има равен брой участия на лява и на дясна кръгла скоба.
2. Ako E съдържа поне една запетая, то във всяко начало на E, завършващо със запетая, броят на участията
на лява кръгла скоба е по-голям от броя на участията на дясна кръгла скоба.
Имайки на разположение тези твърдения, да предположим,
че е налице някое равенство от вида
W(E1,E2...,En) = V(D1,D2...,Dm),
където n и m са положителни цели числа, W и V са думи от W и E1, E2, ..., En, D1, D2, ..., Dm са префиксни изрази над W. Ще трябва да покажем, че в такъв случай имаме и равенствата
W = V, n = m, E1 = D1, E2 = D2, ...., En = Dn.
От предположеното равенство и от обстоятелството, че думите от W не съдържат кръгли скоби, веднага се вижда, че W=V, а това позволява да твърдим, че думата
E1,E2...,En и думата D1,D2...,Dm
са равни. Оттук заключаваме най-напред, че думите E1
и D1 имат една и съща дължина и следователно (понеже са начала на една и съща дума) са равни. Действително, ако допуснем например, че дължината на E1 е по-малка от дължината на D1, то твърдение 2 ще ни позволи да твърдим, че броят на участията на лява кръгла скоба в думата E1 е по-голям от броя на участията на дясна кръгла скоба в същата дума, докато пък според твърдение 1 тези два броя трябва да бъдат равни. От равенството на E1 и D1 следва, че ще бъдат равни също думата ,E2...,En и думата ,D2...,Dm . Значи, ако едната от тях е празна, то и другата ще е празна, тъй че в този случай ще имаме n=m=1 и следователно това, което имаме да докажем, ще е изпълнено. Другата възможност е никоя от думите ,E2...,En и ,D2...,Dm да не е празна. Тогава и двете числа n и m са по-големи от 1 и думите E2,
E3...,En и D2,D3...,Dm ще бъдат равни. Разсъждавайки както преди малко, в този случай ще успеем да получим равенството E2 = D2 и да заключим, че думите ,E3...,En и ,D3...,Dm също са равни. Като повторим тези разсъждения толкова пъти, колкото е необходимо, стигаме до желания резултат.
Забележка 2. Има важни случаи, когато префиксните изрази над W имат еднозначен анализ, въпреки че някои думи от W съдържат кръгли скоби или запетаи. Един такъв случай е онзи, когато базисната азбука съдържа и някакъв вид кавички и се допуска в думи от W да се срещат кръгли скоби или запетаи в части от думата, заградени с кавички. Този случай може да бъде разгледан чрез подходящо изменение на горните разглеждания.
За случаите, когато префиксните изрази над W имат еднозначен анализ, дефинираме понятията функтор и аргументи на един префиксен израз над W. А именно, ако n е положително цяло число, W е дума от W и E1, E2, ..., En са префиксни изрази над W, то думата W наричаме функтор на префиксния израз W(E1,E2...,En), а думите E1, E2, ..., En - негови аргументи (първи, втори, ..., n-ти). За префиксен израз, който е дума от W, приемаме, че тази дума е неговият функтор и че изразът няма аргументи.
Последно изменение: 18.02.2002 г.