Да предположим, че са дадени една азбука А, която по-нататък ще наричаме основна, и още три други азбуки Л, Д и Р, които ще наричаме съответно азбука на левите ограничители, азбука на десните ограничители и азбука на разделителите. Ще искаме никои две от споменатите четири азбуки да нямат общи знаци. За нас ще бъде най-важен случаят, когато азбуката А се състои от главните и малките латински букви, знака _ и десетте цифри, азбуките Л и Д имат само по една буква - съответно лявата кръгла скоба и дясната кръгла скоба, а азбуката Р има за букви знака запетая и знака точка и запетая. Така описаната конкретна четворка от азбуки ще наричаме стандартна. Засега обаче няма в нашите разглеждания да се ограничаваме само с този специален случай.

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

      Пример 1. Нека четворката от азбуките А, Л, Д и Р е стандартната. Нека f е функцията, която преобразува всяка дума w над обединението на четирите азбуки в по-дългата дума, получена от w чрез заграждането й в скоби. Тогава можем да напишем, че е в сила например равенството

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

      Определен вид думи над обединението на азбуките А, Л, Д и Р ще наричаме А,Л,Д,Р-изрази, а по-кратко, макар и по-неточно - изрази над А или просто изрази (когато четворката азбуки А, Л, Д, Р е стандартната, ще наричаме А,Л,Д,Р-изразите стандартни изрази). Дефиницията е индуктивна и се състои от следните две точки:
          1. Всички думи от множеството А* (т.е. всички думи над азбуката А, вкл. и празната дума) са изрази.
          2. Всеки път, когато m е положително цяло число, И₁, И₂, …, И_m−1, И_m са изрази,  л е знак от Л,  д е знак от Д,  р₁, р₂, …, р_m−1 са знаци от Р, а П и С са думи (евентуално празни) от множеството А*, думата

      Пример 2. Всяка от написаните по-долу четири думи е стандартен израз (втората от тях се среща в пример 3 от встъпителните бележки, a в него и в пример 1 от встъпителните бележки се срещат и няколко поддуми на останалите три):

(q(a46,a78),q(a78,a47),q(a47,a46))

p(s(X),a(s(b(X))))

(p(X,a(a(b(b(e))))),d(X))

(d(a(s(b(e))));(p(X2,b(b(e))),d(a(a(X2)))))

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

      Лема 1. В И има равен брой участия на знаци от Л и на знаци от Д.

      Лема 2. Ако И съдържа поне един знак от Р, то във всяко начало на И, завършващо с такъв знак, броят на участията на знаци от Л е по-голям от броя на участията на знаци от Д.

      Имайки на разположение тези твърдения, да предположим, че е налице някое равенство от вида

където m и n са положителни цели числа,  И₁, И₂, …, И_m−1, И_m, И'₁, И'₂, …, И'_n−1, И'_n са изрази,  л и л' са знаци от Л,  д и д' са знаци от Д,  р₁, р₂, …, р_m−1, р'₁, р'₂, …, р'_n−1 са знаци от Р, а П, П', С, С' са думи от А*. Ще трябва да покажем, че в такъв случай имаме и равенствата

От предположеното равенство и от обстоятелството, че думите П и П' не съдържат знаци от азбуката Л, веднага се вижда, че П = П' и л = л'. По подобен начин виждаме, че С = С' и д = д'. Следователно имаме равенството

Оттук заключаваме най-напред, че думите И₁ и И'₁ имат една и съща дължина и следователно (понеже са начала на една и съща дума) са равни. Действително, ако допуснем например, че дължината на И₁ е по-малка от дължината на И'₁, то лема 2 ще ни позволи да твърдим, че броят на участията на знаци от Л в думата И₁ е по-голям от броя на участията на знаци от Д в същата дума, докато пък според лема 1 тези два броя трябва да бъдат равни. От равенството на И₁ и И'₁ следва, че ако няйое от числата m и n е 1, то другото от тях също е 1 и значи твърдението, което имаме да докажем, е вярно. Другата възможност е и двете числа m и n да са по-големи от  1. Тогава имаме равенствата

Разсъждавайки както преди малко, в този случай ще успеем да получим равенството И₂ = И'₂ и да заключим, че ако някое от числата думите m и n е 2, то другото от тях също е 2 и значи твърдението, което имаме да докажем, е вярно. Като повторим подобни разсъждения толкова пъти, колкото е необходимо, стигаме до желания резултат.

      Доказаната еднозначност на представянето на съставните изрази във вида от точка 2 на дефицията дава възможност за всеки такъв израз да въведем наименования за някои негови поддуми, използвани при получаването му. А именно за израз от споменатия вид ние ще наричаме негови префикс и суфикс съответно думата П и думата С, а изразите И₁, И₂, …, И_m−1, И_m ще наричаме негови аргументи (първи, втори, …, m−1-и, m-ти).

      Забележка 3. Не е трудно да се види, че множеството на всички А,Л,Д,Р-изрази е безконтекстен език над обединението на азбуките А, Л, Д и Р и е най-малкият език L над това обединение, удовлетворяващ условието

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

Previous  Next  Contents