Съдържание 
 

ОСИГУРЯВАНЕ НА ЕДНОЗНАЧЕН ПРОЧИТ С ПОМОЩТА НА СКОБИ И РАЗДЕЛИТЕЛИ

      Този въпрос играе подготвителна роля за описанието на формален език, подходящ за нуждите на логическото програмиране и по-специално на програмирането на езика Пролог (за конкретност можем да си мислим за реализацията Strawberry Prolog на този език). Да наречем основна азбука на Пролог азбуката, която се състои от малките и главните латински букви, знака  _  и десетте цифри. Допълнена основна азбука на Пролог ще наричаме азбуката, която се получава от основната азбука на Пролог чрез добавяне на следните четири знака:
( ) , ;
(т.е. на знаците лява кръгла скоба, дясна кръгла скоба, запетая, точка и запетая). Последните два от споменатите четири знака ще наричаме с общото име разделители. За краткост думите над допълнената основна азбука на Пролог ще наричаме в настоящия въпрос просто думи.

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

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

      Забележка 2. Има случаи, когато използването на различни шрифтове е невъзможно или затруднително. В такива случаи можем да си послужим с един друг начин, а именно заграждане в кавички, за да отбележим това, че на определено място дадеии знаци означават не нещо друго, а самите себе си. При използване на този начин равенствата от горната забележка могат да се запишат по следния начин:

f("bf,f") = "(bf,f)",    f(f(θ)) = f("("θ")") = "(("θ"))".

      За коя да е да е дума θ ще означаваме с l(θ) и с r(θ) съответно броя на участията на лява кръгла скоба и броя на участията на дясна кръгла скоба в θ. Думите θ, за които  l(θ) = r(θ),  ще наричаме уравновесени. Ще казваме, че думата θ е допустима, ако тя е уравновесена и за всяко нейно начало λ, което завършва с разделител, имаме неравенството  l(λ) ≥ r(λ),  а ще казваме, че θ е силно допустима, ако тя е уравновесена и за всяко нейно начало λ, което завършва с разделител, имаме строгото неравенство  l(λ) > r(λ)  (условията относно началата на θ, които завършват с разделител, смятаме за изпълнени и в случаите, когато не съществуват такива начала на θ, т.е. когато в θ няма разделители). Ясно е, че всяка силно допустима дума е допустима. Обратното не е вярно (например еднобуквена дума, на която буквата е разделител, не е силно допустима, въпреки че е допустима).

      Очевидно всички думи, в които не участват скоби, са допустими, а думите над основната азбука на Пролог са даже силно допустими. При заграждане на допустима дума в скоби се получава дума, която е силно допустима, т.е. за всяка допустима дума  θ  думата  (θ)  е силно допустима. Действително, нека θ е допустима дума. Тогава

l((θ)) = l(θ)+1 = r(θ)+1 = r((θ))
и за всяко начало  α  на думата  (θ) ,  което завършва с разделител, имаме равенство от вида  α = (β  с някое начало  β  на  θ,  завършващо с разделител, откъдето получаваме, че
l(α) = l(β)+1 ≥ r(β)+1 = r(α)+1 > r(α).
Освен това конкатенацията на всеки две допустими думи е пак допустима дума, а конкатенацията на две силно допустими думи е пак силно допустима дума. За да докажем първото от тези две твърдения, да предположим, че  θ1  и  θ2  са допустими думи и нека  θ = θ1θ2 . Тогава думата  θ  е допустима, защото
l(θ) = l(θ1)+l(θ2) = r(θ1)+r(θ2) = r(θ),
а за всяко начало α на θ, което завършва с разделител, е налице някой от следните два случая: а) α е начало на θ1 и б) α = θ1β  за някое начало β на θ2, завършващо с разделител. В случая а) верността на неравенството l(α)≥r(α) е непосредствено ясна, а в случая б) тя се вижда така:
l(α) = l(θ1)+l(β) = r(θ1)+l(β) ≥ r(θ1)+r(β) = r(α).
Доказателството на второто от твърденията е аналогично. От доказаното разбира се е ясно, че конкатенацията на всякакъв краен брой допустими думи е пак допустима дума, а конкатенацията на всякакъв краен брой силно допустими думи е пак силно допустима дума.

      Наред с отбелязаните по-горе свойства, важна роля по-нататък ще играе следното твърдение.

      Лема за еднозначния прочит. Ако една дума може да се представи във вида
(1) θ1γ1θ2γ2…θn−1γn−1θn ,     
където  n ≥ 1,  θ1 ,  θ2 ,  … ,  θn−1 ,  θn   са силно допустими думи, а  γ1 ,  γ2 ,  … ,  γn−1   са разделители, то представянето й в този вид е единствено.

      Доказателство. Ще опишем един алгоритъм, преобразуващ всяка дума от вида (1), за която са изпълнени формулираните условия, в редицата от думи
(2)θ1γ1 ,  θ2γ2 ,  … , θn−1γn−1 ,  θn .     
За целта ще разгледаме един итеративен процес, който преобразува непразни крайни редици от думи пак в такива редици. Произволна стъпка на процеса може да бъде описана с помощта на следното указание: ако последният член на редицата има уравновесено начало, завършващо с разделител, то заменяме този член с двойка думи, първата от които е най-късото му уравновесено начало, завършващо с разделител, а втората е останалата част от този член след въпросното начало. Процесът завършва тогава, когато се стигне до редица, чийто последен член няма уравновесено начало, завършващо с разделител. Ще покажем, че ако се тръгне от едночленна редица, на която единственият член е дума от вида (1) при изпълнени условията от лемата, то след  n−1  на брой стъпки процесът завършва, при което се получава редицата (2). И наистина, с индукция относно  i,  използваща силната допустимост на думите  θ1 ,  θ2 ,  … ,  θn−1 ,  лесно се показва, че при  i = 0, 1, …, n−1,  ако тръгнем от редицата с единствен член (1), то след  i  на брой стъпки ще стигнем до редицата

θ1γ1 ,  θ2γ2 ,  … , θiγi,  θi+1γi+1θi+2γ2…θn−1γn−1θn, 
(приемаме, че при  i = n−1 изразът  θi+1γi+1θi+2γ2…θn−1γn−1θn  означава  θn ). В частност се получава, че след  n−1  стъпки ще стигнем до редицата (2). Понеже и думата  θn  е силно допустима, с получаването на тази редица процесът завършва.  □

      Пример. Ще проследим как протича процесът от горното доказателство, когато дадената дума е

f(g(a,b),c),f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c)) .
Едночленната редица, с която започва процесът, и последователно получаващите се в хода му други редици са следните (при записването на онези, които са с повече от един член, за отделяне на съседните им членове са използвани интервали вместо запетаи, за да се избегне объркване със запетаите, които са в самите членове): 
f(g(a,b),c),f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),  g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),  g(f(a,b),c),  g(a,f(b,c))  
Полученият резултат показва, че ако дадената дума има представяне от вида, разглеждан в лемата, то при това представяне са в сила равенствата  n=4,  θ1 = f(g(a,b),c) ,  θ2 = f(a,g(b,c)) , θ3 = g(f(a,b),c) , θ4 = g(a,f(b,c)) ,  а разделителите δ1,  δ2 и δ3 са запетаи. Лесно се вижда, че така намерените думи θ1, θ2, θ3 и θ4 са силно допустими, следователно дадената дума наистина има представяне от вида, разглеждан в лемата.

      Забележка 3. Силно допустимите думи θ1, θ2, θ3 и θ4, които се получиха в горния пример, са от вид, който е обичаен за математиката. Думи от подобен вид са обичайни и за езика Пролог. Съществуват обаче и странни силно допустими думи, които не се срещат нито в математиката, нито в Пролог, и едва ли биха могли да имат някаква употреба. Такава е например думата  )((,))( . Всъщност обичайно срещащите се силно допустими думи удовлетворяват едно допълнително условие, което е от значение при някои други въпроси за еднозначност на прочита. То е следното: във всяко начало на думата (независимо дали завършва или не завършва с разделител) броят на левите скоби да бъде не по-малък от броя на десните.

Последно изменение: 17.10.2008 г. По-стара версия (актуална до 17.10.2008 г.)