Съдържание 
 

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

      Този въпрос играе подготвителна роля за описанието на формален език, подходящ за нуждите на логическото програмиране и по-специално на програмирането на езика Пролог (за конкретност можем да си мислим за реализацията 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(α)>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θ2δ2…θn−1δn−1θn ,  където  n≥1,  θ1 ,  θ2 ,  … ,  θn−1 ,  θn   са силно допустими думи, а  δ1 ,  δ2 ,  … ,  δn−1   са разделители, то представянето й в този вид е единствено (приемаме, че при  n=1  изразът  θ1δ1θ2δ2…θn−1δn−1θn  означава  θ1).

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

θ1δ1 ,  θ2δ2 ,  … , θn−1δn−1 ,  θn .
При n=1 това следва веднага от силната допустимост на думата  θ1. Нека сега n>1. Тогава, като се използва силната допустимост на думите  θ1 ,  θ2 ,  … ,  θn−1 ,  с индукция относно i лесно се показва, че при i=0,1,…,n−1, ако тръгнем от редицата с единствен член  θ1δ1θ2δ2…θn−1δn−1θn ,  то след i на брой стъпки ще стигнем, при това без процесът да завърши, до редицата
θi+1δi+1θi+2δ2…θn−1δn−1θn ,  θ1δ1 ,  θ2δ2 ,  … , θiδi
(приемаме, че при i=n−1 изразът θi+1δi+1θi+2δ2…θn−1δn−1θn   означава θn). В частност се получава, че след n−1 стъпки ще стигнем, при това без процесът да завърши, до редицата
θn ,  θ1δ1 ,  θ2δ2 ,  … , θn−1δn−1 .
Понеже и думата  θn  е силно допустима, след още една стъпка се стигнем до редицата
θ1δ1 ,  θ2δ2 ,  … , θn−1δn−1 ,  θ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(a,g(b,c)),g(f(a,b),c),g(a,f(b,c))  f(g(a,b),c),
g(f(a,b),c),g(a,f(b,c))  f(g(a,b),c),  f(a,g(b,c)),
g(a,f(b,c))  f(g(a,b),c),  f(a,g(b,c)),  g(f(a,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, които се получиха в горния пример, са от вид, който е обичаен за математиката. Думи от подобен вид са обичайни и за езика Пролог. Съществуват обаче и странни силно допустими думи, които не се срещат нито в математиката, нито в Пролог, и едва ли биха могли да имат някаква употреба. Такава е например думата  )((,))( . Всъщност обичайно срещащите се силно допустими думи удовлетворяват едно допълнително условие, което е от значение при някои други въпроси за еднозначност на прочита. То е следното: във всяко начало на думата (независимо дали завършва или не завършва с разделител) броят на левите скоби да бъде не по-малък от броя на десните.

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