Да предположим, че е дадена една азбука, съдържаща измежду своите знаци двете кръгли скоби и запетаята (когато по-нататък конкретни знаци от тази азбука се срещат в рамките на друг текст, за избягване на недоразумения ще ги изобразяваме с получерен шрифт). Тази азбука по-нататък ще я наричаме базисна. Ако 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 и всеки съставен префиксен израз има само едно представяне във въпросния втори вид. Едно достатъчно (но не необходимо) условие, за да имат префиксните изрази над 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ўў  също са равни. Като повторим тези разсъждения толкова пъти, колкото е необходимо, стигаме до желания резултат.

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

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

Previous  Next  Contents