|
|
Забележка 1. Когато по-нататък конкретни знаци от гореспоменатата азбука и конкретни думи, съставени от такива знаци, се срещат в текста в ролята именно на такива знаци и думи (а не изпълняват някаква друга роля), за избягване на недоразумения ще ги изобразяваме с прав шрифт с фиксирана широчина на буквите (машинописен шрифт). За по-голяма отчетливост шрифтът ще бъде и получерен (получерен машиношисен шрифт вече сме използвали с подобна цел в някои примери от предходните въпроси). Нека например f е функцията, която преобразува всяка дума ω в по-дългата дума, получена от ω чрез заграждането й в скоби. Тогава можем да напишем, че е в сила например равенството
Забележка 2. Има случаи, когато използването на различни шрифтове е невъзможно или затруднително. В такива случаи можем да си послужим с един друг начин, а именно заграждане в кавички, за да отбележим това, че на определено място дадеии знаци означават не нещо друго, а самите себе си. При използване на този начин равенствата от горната забележка могат да се запишат по следния начин:
За коя да е да е дума ω ще означаваме с l(ω) и с r(ω) съответно броя на участията на лява кръгла скоба и броя на участията на дясна кръгла скоба в ω. Ще казваме, че думата ω е уравновесена (или балансирана), ако е в сила равенството l(ω)=r(ω) и за всяко начало θ на ω имаме неравенството l(θ)≥r(θ) (разбира се достатъчно е да поставим последното изискване само за непразните начала θ на ω, които са различни от ω).
Очевидно думите, в които не участват скоби, (в частност всички думи над основната азбука на Пролог) са уравновесени. Свойството уравновесеност се запазва при заграждане в скоби, т.е. за всяка уравновесена дума ω думата (ω) също е уравновесена; при това за всяко нейно непразно начало θ, което е различно от нея, имаме даже строгото неравенство l(θ)>r(θ). Действително, нека ω е уравновесена дума. Тогава
Забележка 3. Второто изискване в дефиницията за уравновесеност на една дума ω, според което трябва за всяко начало θ на ω да имаме неравенството l(θ)≥r(θ), може да се замени с изискването за всеки край τ на ω да е в сила неравенството l(τ)≤r(τ). Това следва от обстоятелството, че ако е налице първото изискване в дефиницията, т.е. равенството l(ω)=r(ω), то винаги, когато имаме равенството ω=θτ, ще имаме и равенството l(θ)+l(τ)=r(θ)+r(τ), поради което неравенството l(θ)≥r(θ) ще бъде еквивалентно на неравенството l(τ)≤r(τ).
Една дума ще наричаме силно уравновесена, ако тя е уравновесена и не съществува нейно начало θ, завършващо с разделител, за което да е в сила равенството l(θ)=r(θ). Силно уравновесените думи ще наричаме още стандартни изрази.
Забележка 4. Да разгледаме произволна дума от вида ω1δω2 , където δ е разделител, а ω1 и ω2 са уравновесени думи. Тя е уравновесена, понеже е конкатенация на уравновесени думи, но не е силно уравновесена, защото l(ω1δ)=r(ω1δ), въпреки че ω1δ е нейно начало, завършващо с разделител. По този начин виждаме, че не всяка уравновесена дума е силно уравновесена.
Очевидно всички думи над основната азбука на Пролог са силно уравновесени и за всяка уравновесена дума ω думата (ω) е силно уравновесена (тя изобщо не притежава непразно начало θ, различно от нея, за което да е в сила равенството l(θ)=r(θ) ). И силната уравновесеност се запазва при конкатенация. Действително, нека ω=ω1ω2, където ω1 и ω2 са силно уравновесени думи. Тогава думата ω е уравновесена като конкатенация на две уравновесени думи и остава да покажем само, че не съществува нейно начало θ, завършващо с разделител, за което да е в сила равенството l(θ)=r(θ). Да допуснем, че има такова начало θ. Понеже ω1 е силно уравновесена, не е възможно θ да е начало на ω1. Поради това θ=ω1τ, където τ е някое непразно начало на ω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) числата l(δ1ω1) и r(δ1ω1) не могат да бъдат равни. Това обаче противоречи на уравновесеността на ω1, тъй като въпросните две числа са съответно равни на l(ω1) и r(ω1).
Свойството, за което споменахме, може да се изкаже по следния начин.
Лема за еднозначното разпадане. Нека n и n′ са положителни цели числа и имаме равенството
Доказателство. Без ограничение на общността можем да предполагаме, че n≥n′. При това допълнително предположение ще си послужим с индукция относно n. При n=1 неравенството n≥n′ гарантира, че и n′=1, а в такъв случай заключението на доказваното твърдение следва от предположението по тривиален начин. Да предположим сега, че за дадена положителна цяла стойност на n доказваното твърдение е вярно и че за дадено положително цяло число n′, ненадминаващо n+1, дадени силно уравновесени думи ω1, ω2, …, ωn, ωn+1, ω1′, ω2′, …, ωn′−1′, ωn′′ и дадени разделители δ1, δ2, …, δn, δ1′, δ2′, …, δn′−1′ е в сила равенството
|
|
Дата на предходната версия: | 25.03.2004 |
Дата на настоящата версия: | 28.02.2005 |