Previous  Next  Contents
 

 

УРАВНОВЕСЕНИ ДУМИ

      Този въпрос играе подготвителна роля за описанието на формален език, подходящ за нуждите на логическото програмиране. Ще се занимаем с някои видове думи над основната азбука на Пролог, разширена със следните четири знака: лява кръгла скоба, дясна кръгла скоба, запетая, точка и запетая. Последните два от тях ще наричаме с общото име разделители, а азбуката, за която става дума  -  допълнена основна азбука на Пролог. За краткост думите над тази азбука ще наричаме в настоящия въпрос просто думи.

      Забележка 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(ω) = l1)+l2) = r1)+r2) = r(ω),
а за всяко начало θ на ω е налице някой от следните два случая: а) θ е начало на ω1 и б) θ = ω1τ  за някое начало τ на ω2. В случая а) верността на неравенството l(θ)≥r(θ) е непосредствено ясна, а в случая б) тя се вижда така:
l(θ) = l1)+l(τ) = r1)+l(τ) ≥ r1)+r(τ) = r(θ).
От доказаното разбира се е ясно, че конкатенацията на всякакъв краен брой уравновесени думи е пак уравновесена дума.

      Забележка 3. Второто изискване в дефиницията за уравновесеност на една дума ω, според което трябва за всяко начало θ на ω да имаме неравенството l(θ)≥r(θ), може да се замени с изискването за всеки край τ на ω да е в сила неравенството l(τ)≤r(τ). Това следва от обстоятелството, че ако е налице първото изискване в дефиницията, т.е. равенството l(ω)=r(ω), то винаги, когато имаме равенството ω=θτ, ще имаме и равенството l(θ)+l(τ)=r(θ)+r(τ), поради което неравенството l(θ)≥r(θ) ще бъде еквивалентно на неравенството l(τ)≤r(τ).

      Една дума ще наричаме силно уравновесена, ако тя е уравновесена и не съществува нейно начало θ, завършващо с разделител, за което да е в сила равенството l(θ)=r(θ). Силно уравновесените думи ще наричаме още стандартни изрази.

      Забележка 4. Да разгледаме произволна дума от вида  ω1δω2 ,  където δ е разделител, а ω1 и ω2 са уравновесени думи. Тя е уравновесена, понеже е конкатенация на уравновесени думи, но не е силно уравновесена, защото l1δ)=r1δ), въпреки че ω1δ е нейно начало, завършващо с разделител. По този начин виждаме, че не всяка уравновесена дума е силно уравновесена.

      Очевидно всички думи над основната азбука на Пролог са силно уравновесени и за всяка уравновесена дума  ω  думата  (ω)  е силно уравновесена (тя изобщо не притежава непразно начало θ, различно от нея, за което да е в сила равенството l(θ)=r(θ) ). И силната уравновесеност се запазва при конкатенация. Действително, нека ω=ω1ω2, където ω1 и ω2 са силно уравновесени думи. Тогава думата ω е уравновесена като конкатенация на две уравновесени думи и остава да покажем само, че не съществува нейно начало θ, завършващо с разделител, за което да е в сила равенството l(θ)=r(θ). Да допуснем, че има такова начало θ. Понеже ω1 е силно уравновесена, не е възможно θ да е начало на ω1. Поради това θ=ω1τ, където τ е някое непразно начало на ω2. Ще имаме равенствата

l(θ) = l1)+l(τ),   r(θ) = r1)+r(τ),
от които поради равенството на левите им страни и равенството l1)=r1) следва равенството l(τ)=r(τ). То обаче не е възможно, защото τ е начало на ω2, завършващо с разделител.

      Забележка 5. Второто изискване в дефиницията за силна уравновесеност на една дума ω, според което не бива в никое начало на ω, завършващо с разделител, да имаме равен брой участия на леви и десни скоби, може да се замени с изискването такъв равен брой да не е налице в никой край на ω, започващ с разделител. Това следва от обстоятелството, че ако ω е уравновесена дума и имаме равенството  ω=φδψ ,  където δ е разделител, то ще имаме и равенството l(φ)+l(ψ)=r(φ)+r(ψ), поради което равенството l(φδ)=r(φδ) ще бъде еквивалентно на равенството l(δψ)=r(δψ) (последните две равенства са съответно еквивалентни на равенствата l(φ)=r(φ) и l(ψ)=r(ψ) ).

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

      В основата на това свойство лежи следното обстоятелство: никоя дума от вида  δω ,  където δ е разделител, а ω е силно уравновесена дума, не е край на друга дума от същия вид  (и аналогично, никоя дума от вида  ωδ ,  където ω е силно уравновесена дума, а δ е разделител, не е начало на друга дума от същия вид). За да се убедим във верността на първото от току-що изказаните две твърдения (второто се доказва аналогично), да допуснем, че за някои два разделителя δ1 и δ2 и някои две силно уравновесени думи ω1 и ω2 думата δ1ω1 е край на думата δ2ω2, като при това думите δ1ω1 и δ2ω2 са различни. Тогава δ1ω1 ще бъде край на ω2 и значи (поради силната уравновесеност на ω2) числата l1ω1) и r1ω1) не могат да бъдат равни. Това обаче противоречи на уравновесеността на ω1, тъй като въпросните две числа са съответно равни на l1) и r1).

      Свойството, за което споменахме, може да се изкаже по следния начин.

      Лема за еднозначното разпадане. Нека n и n са положителни цели числа и имаме равенството

ω1δ1ω2δ2ωn1δn1ωn = ω1δ1ω2δ2ωn1δn1ωn ,
където  ω1, ω2, , ωn1, ωn, ω1, ω2, , ωn1, ωn  са силно уравновесени думи, а  δ1, δ2, , δn1, δ1, δ2, , δn1  са разделители (приемаме. че лявата страна на равенството е ω1, когато n=1, и дясната страна на равенството е ω1, когато n=1). Тогава  n=n ωii  при  i=1,2,,n  и  δii  при  i=1,2,,n1 .

      Доказателство. Без ограничение на общността можем да предполагаме, че nn. При това допълнително предположение ще си послужим с индукция относно n. При n=1 неравенството nn гарантира, че и n=1, а в такъв случай заключението на доказваното твърдение следва от предположението по тривиален начин. Да предположим сега, че за дадена положителна цяла стойност на n доказваното твърдение е вярно и че за дадено положително цяло число n, ненадминаващо n+1, дадени силно уравновесени думи  ω1, ω2, , ωn, ωn+1, ω1, ω2, , ωn1, ωn  и дадени разделители  δ1, δ2, , δn, δ1, δ2, , δn1  е в сила равенството

ω1δ1ω2δ2ωnδnωn+1 = ω1δ1ω2δ2ωn1δn1ωn .
Ще докажем, че  n+1=n,  ωii  при  i=1,2,,n+1  и  δii  при  i=1,2,,n . Преди всичко отбелязваме, че не е възможно числото n да е 1, защото тогава дясната страна на предположеното преди малко равенство би била силно уравновесената дума ω1, докато лявата му страна със сигурност не е силно уравновесена, както това се вижда от забележка 4 и запазването на уравновесеността при конкатенация. Значи n=k+1 за някое положително цяло число k и предположеното равенство добива вида
ω1δ1ω2δ2ωnδnωn+1 = ω1δ1ω2δ2ωkδkωk+1 .
От това равенство следва, че някоя от думите δnωn+1 и δkωk+1 е край на другата и значи те съвпадат. Оттук получаваме, че  ωn+1k+1,   δnk  и
ω1δ1ω2δ2ωn = ω1δ1ω2δ2ωk .
Току-що полученото равенство заедно с индуктивното предположение позволява да твърдим, че n=k ωii  при  i=1,2,,n  и  δii  при  i=1,2,,n1 . С това показахме, че наистина  n+1=n,  ωii  при  i=1,2,,n+1  и  δii  при  i=1,2,,n .  
 
 Previous  Next  Contents
 
Дата на предходната версия: 25.03.2004
Дата на настоящата версия: 28.02.2005