Да предположим, че е дадена една азбука, съдържаща измежду своите знаци двете кръгли скоби и запетаята. Тази азбука по-нататък ще я наричаме базисна. Когато по-нататък конкретни знаци от базисната азбука се срещат в рамките на друг текст в ролята именно на такива знаци, за избягване на недоразумения ще ги изобразяваме с получерен шрифт.

    Пример 1. Нека f е функцията, която преобразува всяка дума w над базисната азбука в по-дългата дума, получена от w чрез заграждането й в скоби. Тогава можем да напишем, че за всяка дума w над базисната азбука е в сила равенството f(w)=(w). Тук скобите в дясната страна на равенството са употребени в ролята на знаци от базисната азбука, докато скобите в лявата страна изпълняват обичайната си роля в означение на прилагане на функция към аргумент. Като разграничаваме въпросните две роли, няма да имаме трудности и в тълкуването например на такива равенства:

    Забележка 1. Един друг начин за отбелязване на това, че на определено място дадеии знаци означават не нещо друго, а самите себе си - това е заграждането в кавички. При такова уславяне равенствата от горния пример могат да се запишат по следния начин:

    Ако W е едно множество от думи над базисната азбука, то някои думи над нея ще наричаме префиксни изрази над W. Дефиницията е индуктивна: така ще наричаме думите от W и всички думи от вида w(T₁,T₂...,T_n), където n е положително цяло число, w е дума от W и T₁, T₂, ..., T_n са префиксни изрази над W (при n=1 считаме, че думата  ,T₂...,T_n  е празна, докато при n>1 тя очевидно не е празна). Префиксните изрази от втория вид ще наричаме съставни. Ще казваме, че префиксните изрази над W имат еднозначен анализ, ако никой съставен префиксен израз над W не принадлежи на самото W и всеки съставен префиксен израз има само едно представяне във въпросния втори вид. Съвсем лесно могат да се дадат примери, при които е нарушено първото от тези две условия. Сега ще дадем един пример, в който е нарушено второто от тях.

    Пример 2. Нека множеството W съдържа като елементи еднобуквената дума с единствена буква запетая и двубуквената дума, състояща се от две запетаи. Тогава думата ,(,,,,) е префиксен израз над W с две различни представяния във вида w(T₁,T₂), където w е от W, а T₁ и T₂ са префиксни изрази над W: и при двете представяния w е запетая, но при едното представяне T₁ и T₂ се състоят съответно от една и от две запетаи, а при другото положението е обратното.

    Едно достатъчно (но не необходимо) условие, за да имат префиксните изрази над W еднозначен анализ - това е условието в думите от W да не се срещат нито кръгли скоби, нито запетаи. За да се убедим в достатъчността на изказаното условие, да предположим, че то е изпълнено. Тогава поради наличието на kръгли скоби във всеки съставен префиксен израз над W не е възможно такъв израз да принадлежи на самото W. Остава да покажем, че всеки съставен префиксен израз над W има само едно представяне във вида w(T₁,T₂...,T_n), където n е положително цяло число, w е дума от W и T₁, T₂, ..., T_n са префиксни изрази над W. Това може да се направи по следния начин. Първо с индукция, съобразена с дефиницията за префиксен израз над W, се доказват следните две леми (доказателствата им са лесни и ги оставяме за самостоятелно обмисляне):

    Лема 1. Във всеки префиксен израз над W броят на участията на лява кръгла скоба е равен на броя на участията на дясна кръгла скоба.

    Лема 2. Във всяко начало на префиксен израз над W , завършващо със запетая, броят на участията на лява кръгла скоба е по-голям от броя на участията на дясна кръгла скоба.

    Имайки на разположение тези леми, да предположим, че е налице някое равенство от вида

където n и nў са положителни цели числа, w и wў са думи от W и T₁, T₂, ..., T_n, T₁ў, T₂ў, ..., T_nўў са префиксни изрази над W. Ще трябва да покажем, че в такъв случай имаме и равенствата

От предположеното равенство и от обстоятелството, че думите от W не съдържат кръгли скоби, веднага се вижда, че w=wў, а това позволява да твърдим, че думите T₁,T₂...,T_n  и  T₁ў,T₂ў...,T_nўў  са равни. Оттук заключаваме най-напред, че думите T₁ и T₁ў имат една и съща дължина и следователно (понеже са начала на една и съща дума) са равни. Действително, ако допуснем например, че дължината на T₁ е по-малка от дължината на T₁ў , то лема 2 ще ни позволи да твърдим, че броят на участията на лява кръгла скоба в думата T₁ е по-голям от броя на участията на дясна кръгла скоба в същата дума, докато пък според лема 1 тези два броя трябва да бъдат равни. От равенството на T₁ и T₁ў следва, че ще бъдат равни и думите  ,T₂...,T_n  и  ,T₂ў...,T_nўў . Значи, ако едната от тях е празна, то и другата ще е празна, тъй че в този случай ще имаме n=nў=1 и следователно това, което имаме да докажем, ще е изпълнено. Другата възможност е никоя от думите  ,T₂...,T_n  и  ,T₂ў...,T_nўў да не е празна. Тогава и двете числа n и nў са по-големи от 1 и думите T₂ ,T₃...,T_n и T₂ў,T₃ў...,T_nўў ще бъдат равни. Разсъждавайки както преди малко, в този случай ще успеем да получим равенството T₂=T₂ў и да заключим, че думите  ,T₃...,T_n  и  ,T₃ў...,T_nўў  също са равни. Като повторим тези разсъждения толкова пъти, колкото е необходимо, стигаме до желания резултат.

    Забележка 2. Има важни случаи, когато префиксните изрази над  W имат еднозначен анализ, въпреки че някои думи от W съдържат кръгли скоби или запетаи. Един такъв случай е онзи, когато базисната азбука съдържа и някакъв вид кавички и се допуска в думи от W да се срещат кръгли скоби или запетаи в части от думата, заградени с кавички. Този случай може да бъде разгледан чрез подходящо изменение на горните разглеждания.
 

Последно изменение: 30.07.2001 г.
 

Previous  Next  Contents