Редовни езици и крайни автомати. Редовен език Редовни езици и държавни машини

Редовни комплектии регулярни изрази

Редовни комплекти

В този раздел ще разгледаме клас от набори от вериги над краен речник, които са много лесни за описание с формули от някакъв вид. Тези комплекти се наричат ​​редовни.

Определение 1.Позволявам V 1 и V 2 - много вериги. Дефинираме три операциина тези комплекти.

Обединение: V 1 V 2 =(|   V 1 ) или   V 2 .

Конкатенация (продукт, слепване): Vl V2 = (|  V 1 ,  V 2 ) Знакът на операцията за конкатенация обикновено се пропуска.

Пример: V, = (abc, ba), V 2 = (b, cb). V1V2 =(abcb, abccb, bab, bacb).

Означаваме с V n произведението на n множества V:V n =VV...V,V° =() (тук  е празен низ).

Пример: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Итерация: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Пример: V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...).

Определение 4.13.Клас на регулярни набори над краен речник V дефинирамстава така:

съюз ST;

конкатенация ST;

итерация S* и T*.

5. Ако едно множество не може да бъде конструирано чрез краен брой приложения на правила 1-4, тогава то е неправилно.

Примери за правилни набори: (ab, ba)* (aa); (b)((c)(d, ab)*). Примери за неправилни множества: (a n b n | n > 0); ( | във веригата  броят на срещанията на знаците a и b е еднакъв).

Регулярни изрази

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

Определение 2.Клас регулярен израз над крайния речник V дефинирамстава така:

тяхната сума R1+R2;

техният продукт R1R2;

тяхната итерация R1* и R2*.

4. Ако изразът не е изграден чрез краен брой прилагания на правилата 1-3, тогава той не е правилен.

Знакът на продукта може да бъде пропуснат. За да се намали броят на скобите, както във всяка алгебра, се използват приоритетите на операциите: итерацията има най-висок приоритет; по-малко приоритетна работа; добавянето е с най-нисък приоритет.

Примери за регулярни изрази: ab + ba*; (aa)*b + (c + dab)*.

Очевидно регулярните множества и регулярните изрази са много близки. Но те са различни същности: редовният набор е набор от вериги (обикновено безкрайни) и регулярният израз еформула, която схематично показва как съответният регулярен набор е конструиран с помощта на изброените по-горе операции(и тази формула е крайна).

Нека R^ е регулярният набор, съответстващ на регулярния израз R. Тогава:

Така регулярният израз е крайна формула, която дефинира безкраен брой низове, тоест език.

Нека да разгледаме примери за регулярни изрази и съответните им езици.

Редовен израз	Съответстващ език
	Всички низове, започващи с b, последвани от произволен брой знаци a
	Всички низове от a и b, съдържащи точно две срещания на b
	Всички низове от a и b, които съдържат b само по двойки
(a+b)*(aa+bb)(a+b)*	Всички низове от a и b, съдържащи поне една двойка съседни a или b
(0+1)*11001(0+1)*	Всички низове от 0 и 1, съдържащи подниз 11001
	Всички низове от a и b, които започват с a и завършват с b

Очевидно набор от низове е правилен тогава и само ако може да бъде представен чрез регулярен израз. Същият набор от низове обаче може да бъде представен с различни регулярни изрази, например набор от низове, състоящ се от символи a и съдържащ поне две a, може да бъде представен с изрази: aa*a; а*ааа*; ааа*; а*аа*аа* и т.н.

Определение 3.Два регулярни израза R1 и R2 се наричат ​​еквивалентни (означават Rl = R2) ако и само акоР1 ^ = Р2 ^ .

Така aa*a = a*aaa* = aaa* = a*aa*aa*. Възниква въпросът как да се определи еквивалентността на два регулярни израза.

Теорема1 . За всеки регулярен изразР, С и T справедливо:

Тези отношения могат да бъдат доказани чрез проверка на равенството на съответните набори от вериги. Те могат да се използват за опростяване на регулярни изрази. Например: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Следователно b (b + aa*b) = ba*b, което не е очевидно.

Теорема на Клийн

Регулярните изрази са най-добрите формули, които дефинират регулярните езици. Но крайните автомати имат същото свойство - те също дефинират езици. Възниква въпросът: как се отнасят един към друг класовете езици, дефинирани от крайни автомати и регулярни изрази? Обозначете И много автоматични езици, R е набор от редовни езици. Стивън Клийн, американски математик, доказва следната теорема.

Теорема2 . (Теорема на Клийн.) Класовете на регулярните множества и автоматните езици съвпадат, т.е. А = Р .

С други думи, всеки автоматен език може да бъде дефиниран чрез формула (регулярен израз) и всеки регулярен набор може да бъде разпознат от краен автомат. Ще докажем тази теорема конструктивно, в две стъпки. На първата стъпка ще докажем, че всеки автоматен език е регулярен набор (или, което е същото, за всеки краен автомат можем да конструираме регулярен израз, който указва езика, разпознат от този автомат). На втората стъпка доказваме, че всяко редовно множество е автоматен език (или, което е същото, от всеки регулярен израз можем да конструираме краен автомат, който позволява точно вериги от съответното редовно множество).

Нека въведем модела на графа на прехода като обобщение на модела на крайния автомат. Графът на прехода има един начален и произволен брой крайни върхове, а насочените ребра са маркирани, за разлика от крайния автомат, не със символи, а с регулярни изрази. Графът на прехода допуска верига a if апринадлежи към множеството вериги, описани от произведението на регулярни изрази R 1 R 2 ...R n , които маркират пътя от началния връх до един от крайните върхове. Наборът от вериги, позволени от графа на прехода, образува езика, разрешен от него.

Ориз. 1. Графика на прехода

На фиг. 1 показва графика на прехода, която позволява например веригата abbca, тъй като пътят s->r->p->s->r->q, който води до крайното състояние q, е маркиран с веригата от регулярни изрази ab* c*а. Краен автомат е специален случай на преходна графа и следователно всички езици, които са разрешени от автомати, също са разрешени от преходни графи.

Теорема 3.Всеки автоматен език е нормален набор, A  Р.

Доказателство. Преходен граф с един начален и един краен връх, чието единствено ребро от началния до крайния връх е обозначено с регулярния израз R, допуска езика R ^ (фиг. 1).

Ориз. 2. Граф на преход, допускащ регулярен език FT

Нека сега докажем, че всеки автоматичен език е редовен набор, като редуцираме всеки преходен график, без да променяме езика, който допуска, до еквивалентна форма (фиг. 2).

Всеки краен автомат и всеки преходен граф винаги могат да бъдат представени в нормализирана форма, в която има само един начален връх само с изходящи ребра и само един краен връх само с входящи ребра (фиг. 3).

Ориз. 3. Преходен граф с един начален и един краен връх

С преходна графика, представена в нормализирана форма, могат да се извършат две редукционни операции - редуциране на ръбове и редукция на върха - като същевременно се запази езикът, разрешен от тази преходна графика:

а) намаляване на ръба:

б ) намаляване на върха (замяната се извършва за всеки път, минаващ през върха p, с последващото му изхвърляне като недостижимо състояние):

Очевидно всяка операция на редукция не променя езика, разпознат от графа на прехода, но намалява или броя на ръбовете, или броя на върховете, и в крайна сметка редукциите ще доведат графа на прехода до формата, показана на фиг. 2. Теоремата е доказана: всеки автоматен език е редовно множество.

Пример

Нека е даден краен автомат A:

Изграждаме еквивалентна графика на преход в нормализирана форма.

Намаляване на върха 3:

Намаляване на дъгата и прилагане на правилото R = R:

Намаляване на върха 2:

Намаляване на дъга и връх 1:

Така езикът, разпознат от автомат A, е даден от регулярния израз: R A = b+(a+bb)(b+ab)*a.

Нека докажем теоремата на Клийн в другата посока.

Теорема 2.Всеки нормален набор е автоматен език: R А.

Доказателство.Нека покажем, че за всеки регулярен израз R (възможно недетерминиран) краен автомат A r може да бъде конструиран, който разпознава езика, определен от R. Ще дефинираме такива автомати рекурсивно.

(началното и крайното състояние на A се комбинират).

Пример(продължение)

Редовните граматики, крайните автомати и регулярните множества (и регулярните изрази, които ги обозначават) са три различни начина за дефиниране на регулярни езици.

Изявление

Един език е RM тогава и само ако е даден от ляволинейна (дяснолинейна) граматика. Език може да бъде дефиниран от ляво-линейна (дясно-линейна) граматика тогава и само ако е редовно множество.

Един език е PM тогава и само ако е определен от държавна машина. Един език се разпознава от държавна машина тогава и само ако е PM.

И трите метода са еквивалентни. Има алгоритми, които позволяват за език, определен по един от посочените начини, да се конструира друг метод, който дефинира същия език. Подробно описание на тези алгоритми е достъпно в литературата (вижте списъка).

Например, за да се намери регулярен израз за език, даден от дясна линейна граматика, е необходимо да се конструира и реши система от уравнения с регулярни коефициенти.

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

За да се изгради CA въз основа на известна регулярна граматика, тя трябва да бъде намалена до автоматична форма. Наборът от автоматни състояния ще съответства на набора от нетерминални символи на граматиката. 2.3.2 Свойства на обикновените езици

Множеството се нарича затворено по отношение на някаква операция, ако в резултат на извършването на тази операция върху някой от неговите елементи се получава нов елемент, който принадлежи на същото множество.

Редовните набори са затворени при операциите на пресичане, обединение, добавяне, итерация, конкатенация, промяна на имена на символи и заместване на низове за символи.

Много проблеми са разрешими за обикновени езици, които са неразрешими за други видове езици. Например, следните проблеми са разрешими, независимо по какъв начин е указан езикът:

Проблем с еквивалентността: Дадени са два редовни езика L 1 (V) и L 2 (V). Необходимо е да се установи дали са еквивалентни.

Проблемът за верижната принадлежност към език. Даден е нормален език L(V), низ от символи V * . Необходимо е да се провери дали тази верига принадлежи на езика.

Проблемът за празнотата на езика. Даден е нормален език L(V). Необходимо е да се провери дали този език е празен, т.е. намерете поне една верига, L(V).

Понякога е необходимо да се докаже дали даден език е правилен по дължина. Ако е възможно да се посочи този език по един от разгледаните начини, тогава той е нормален. Но ако не може да се намери такъв начин, не се знае дали езикът не е нормален или просто не е било възможно да се намери начин да се уточни. Има лесен метод за проверка дали въпросният език е нормален. Доказано е, че ако за някакъв език т.нар лема за растеж, тогава е редовен. Ако тази лема не е изпълнена, тогава езикът не е правилен.

Лемата за растеж се формулира по следния начин. Като се има предвид нормален език и достатъчно дълъг низ от знаци, принадлежащ на този език, тогава той може да съдържа непразен подниз, който може да се повтаря произволно много пъти, и всички низове, получени по този начин, също ще принадлежат към разглеждания нормален език.

Формално лемата се записва по следния начин. Ако е даден език L, тогава константата p>0, така че ако L и p, тогава веригата може да бъде записана във формата, където 0

Пример. Да разгледаме езика L=(a n b n n>0). Нека докажем, че това не е редовно, използвайки лемата за растежа на езиците.

Нека този език е правилен, тогава лемата за растеж трябва да е в сила за него. Нека вземем някаква верига на този език = a n b n и я запишем във формата. Ако a + или b + , тогава низът i не принадлежи към езика за нито едно i, което противоречи на условията на лемата. Ако a + b + , тогава низът 2 също не принадлежи на езика L. Получихме противоречие, следователно езикът не е правилен.

Теория на автоматите е разделът за теория системи за управление, който изучава математически модели на преобразуватели на дискретна информация, т.нар картечници. От определена гледна точка такива преобразуватели са както реални устройства (компютри, автомати, живи организми и т.н.), така и абстрактни системи (например формална система, аксиоматични теории и т.н.), което прави възможно прилагането на теорията на автомати в различни научни и приложни изследвания. Теорията на автоматите е най-тясно свързана с математическата логика и теорията на алгоритмите. По-специално, разрешимостта на някои формални изчисления се доказва с помощта на теорията на автоматите.

Друг основен фокус на този курс е формален език 1 е произволен набор от думи от някаква азбука. Значението на формалните езици за теоретичната компютърна наука се дължи на факта, че най-простият и удобен модел на данни, използван в компютърните програми, е крайна последователност, всеки елемент от която е взет от някакъв предварително фиксиран краен набор. Тъй като формалните езици, използвани в приложенията, обикновено са безкрайни, е необходим начин за описание на официалния език по краен начин. В този курс ще изучаваме 3 класически средства за такова описание: автомати, регулярни изразии генеративни граматики.

Въведение

1. Първоначални концепции на теорията на формалните езици

Да разгледаме непразно крайно множество НО, състоящ се от знаци ( а 1 , …, а к). Ще се обадим НО по азбучен ред , а неговите символи са писма . Всяка крайна последователност от букви в тази азбука се нарича дума (верига или низ ): w=а 1 а 2 …а н- дума ( а аз А), |w| - дължината на думата (броят на буквите, които съставляват думата и всеки знак се среща толкова пъти, колкото се среща в w). Чрез | w| bобозначават броя на срещанията на символа bс една дума w.

Безкрайна последователност от букви от азбуката НОНаречен супердума , - супердума от безкраен брой букви а. празен е дума, която не съдържа никакви букви. Означава се с . Очевидно ||=0.

- много думи от азбуката НОдължина н. Набор от всички думи от азбуката НО(включително супердуми) се обозначава НО*. Това множество е изброимо, тъй като е обединение на изброим брой крайни множества
. Наборът от всички непразни думи в азбуката НОозначено НО+ . Ако А={а), тогава НО*={а)* ще се означава с а*.

Всяко подмножество
Наречен език (формален език ) над азбуката НО.

Ако хи г- думи на езика
, след това думата ху(резултатът от приписването на думата прив края на думата х) е наречен конкатенация (съединител на кола , работа ) думи хи при.
(нслед като вземем х). Да сложим
.

Те казват думата х – поддума думите при, ако г=uxvза някои думи uи v. Всички поддуми на думите на езика
форма набор от поддуми език Л, което се означава с Subw( Л).

Примери. 1. ба 3 =бааа,
- тази дума има поддуми аб, аба, баи т.н.

2. Задайте ( а, абб) - език (окончателен) над азбука ( а, b}.

3. Много
е език над азбуката ( а, b). Този език е безкраен, съдържа думи b, ба, аба, баа, абаа, бааа, аабаа, абаааи т.н.

Тъй като всеки език е набор, може да се разгледат операциите за обединение, пресичане и разлика на езици, дадени върху една и съща азбука. Да, език
, където
, се нарича езиково допълнение Лпо отношение на азбуката НО. И ако  винаги е включено в НО* след това език
може или не може да съдържа . В последния случай
.

Позволявам ,
. Тогава езикът се нарича конкатенация (съединител на кола , работа ) езици и . При което
,
(нпъти), ако н>0.

Примери. 1. Ако
,
,тогава .

2. Ако L=(0, 01), тогава
.

Повторение език Лнаречен език
(тази операция се нарича още звезда Клийн ). език
Наречен положителна итерация език Л.

Пример. Ако А={а, b) и Л={аа, аб, ба, bb), тогава
.

Обжалване или в огледален образ думите wнарича думата w Р, в който буквите на думата wвървете в обратен ред. Например ако w=бак, тогава

Позволявам
. След това език
Наречен обжалване език Л.

Всяко начало на дума ще бъде извикано префикс и всеки край на една дума - наставка . Например ако г=xv, тогава х- префикс на думата при(обозначаване - х[г), а v- наставка на думата при(обозначаване - v]г). Очевидно празната дума е както префикс, така и наставка на всяка дума. Всички префикси на думите на езика
форма набор от префикси този език: Pref( Л)
. Подобно на Suf( Л)
-м набор от суфикси език
.

Ако езикът Лтакова, че дума няма Лне е префикс (наставка) на друга дума Л, тогава те казват, че Лима префикс (наставка) Имот .

Позволявам НО 1 и НО 2 - азбуки. Ако дисплеят f:
отговаря на условието за всички думи
и
, след това картографирането fНаречен хомоморфизъм .

Забележки. 1. Може да се докаже, че ако fтогава е хомоморфизъм
.

2. Хомоморфизмите не винаги са биекции, но всеки хомоморфизъм се определя уникално от неговите стойности на еднобуквени думи.

3. Прилагане на хомоморфизма към езика Л, получаваме друг език f(Л).

Ако f:
е хомоморфизъм,
и
, след това през f(Л 1) езикът е посочен
, и през
определен език
, и самото картографиране
Наречен хомоморфна инверсия .

Примери. 1. Да кажем, че искаме да заменим всяко появяване на знака 0 в низа със знака аи всяко появяване на 1 е включено bb. Тогава можем да дефинираме хомоморфизъм fтака
и
. Ако
, тогава
.

2. Нека fе хомоморфизъм, за който
и
. Тогава
и
.

В тази глава започваме изложението на елементите от теорията на формалните езици.

Под „формален език“ имаме предвид, че представените тук резултати се използват предимно в описанието на изкуствени езици, измислени от хора за специални цели, като езици за програмиране. Но няма непреодолима бариера между специално изобретените изкуствени (формални) езици и спонтанно възникващите и развиващи се естествени езици. Оказва се, че естествените езици се характеризират със сложни граматически правила, т.е. са доста строго формализирани и дори най-"научно разработеният" език за програмиране съдържа "тъмни места", чието недвусмислено разбиране е проблем.

Когато изучавате езици, трябва да имате предвид три основни аспекта.

Първият е езиков синтаксис . Езикът е някакъв набор от „думи“, където „дума“ е определена крайна последователност от „букви“ – символи на някаква предварително фиксирана азбука. Термините "буква" и "дума" могат да се разбират по различни начини (математическата дефиниция на тези термини ще бъде дадена по-долу). Така че "буквите" наистина могат да бъдат буквите от азбуката на някакъв естествен или формален език, например руски език или език за програмиране "Паскал". Тогава "думите" ще бъдат последните поредици от "букви": крокодил", " цяло число". Такива думи се наричат ​​"лексеми". Но "буква" може да бъде "дума" ("лексема") като цяло. Тогава "думите" са изречения на естествен език или програма на език за програмиране. Ако някои набор от "букви" е фиксиран, тогава не всяка последователност от тях ще бъде "дума", т.е. елексема" на даден език, а само такава последователност, която се подчинява на определени правила. Думата "крыкадил" не е руска лексема, а думата "ифф" не е лексема на Паскал. Изречението „Обичам те“ не е правилно изречение на руски език, точно както нотацията „х:= =t“ не е правилно написан оператор за присвояване „Паскал“. Синтаксисът * на езика е система от правила, според които е възможно да се изграждат "правилни" поредици от "букви". Всяка дума от даден език се характеризира с определена структура, специфична за този конкретен език. Тогава е необходимо, от една страна, да се разработят механизми за изброяване или генериране на думи с дадена структура, а от друга страна, механизми за проверка на принадлежността на дадена дума към даден език. На първо място, точно тези механизми се изучават от класическата теория на формалните езици.

Вторият аспект е езикова семантика . Семантиката** включва съпоставяне на думите на езика с определено „значение“, Значение". Например, когато пишем математическа формула, трябва да следваме определени синтактични правила (подреждане на скоби, изписване на символи, ред на символите и т.н.). ), но освен това формулата има съвсем определено значение, означава нещо.

Езикът е средство за комуникация, предаване на информация. Ако искаме да бъдем разбрани, трябва не само синтактично правилно, спазвайки правилния ред на буквите в думата и думите в изречението, да изграждаме речта си, но и да се грижим за нейния смисъл, за онези идеи, които изразяваме в речта. Математическите теории за "смисъла" са сравнително скорошни и в допълнение към следващата глава ще разгледаме съвсем накратко някои подходи към математическото описание на семантиката на езиците за програмиране.

* Думата "синтаксис" произлиза от старогръцките "syn" - "заедно" и "taxis" - "ред, ред". По този начин синтаксисът може да се разбира като "композиция".

** От старогръцките думи "sema" - "знак, знак" и "semanticos" - "обозначаващ".

И накрая, третият аспект е езикова прагматика . Прагматиката е свързана с целите, които носителят на езика си поставя: например, човек прави реч, имайки цели, които не са свързани със синтаксиса, не със семантиката на езика, на който той говори или пише, но, да речем , с получаване на определени суми пари. Прагматиката вече е по-скоро социално-философска дисциплина, засягаща целенасочената дейност на индивида. Няма да го докоснем ни най-малко.

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

• Азбука, дума, език

• Генеративни граматики

  Както вече беше отбелязано, класическата теория на формалните езици изучава предимно синтаксиса на даден език. Той въвежда математически модел на синтаксиса, който описва механизмите за генериране и разпознаване на "добре оформени" низове. В този раздел ще разгледаме първия от тези механизми.

знаем операциите за комбиниране на езици. Ние дефинираме операциите на конкатенация и итерация (понякога наричани затваряне на Kleene).

Нека L 1 и L 2 са езици в азбуката

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

Нека въведем обозначението за "степените" на езика L:

Така L i съдържа всички думи, които могат да бъдат разделени на i последователни думи от L .

Итерация (L) * на езика L се формира от всички думи, които могат да бъдат разделени на няколко последователни думи от L:

Може да се представи с помощта на степени:

Често е удобно да се разглежда "скъсена" итерация на език, който не съдържа празната дума, ако тя не съществува в езика: . Това не е нова операция, а просто удобна стенограма за израза.

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

Следващата таблица дава формалната индуктивна дефиниция регулярни изразивърху азбуката и езиците, които представляват.

Израз r	Lr език
	L a =(a)
Нека r 1 и r 2 са	L r1 и L r2 -представени
регулярни изрази.	техните езици.
Тогава следните изрази
са редовни	и представляват езици:
r=(r1+r2)
r=(r1circr2)
r=(r 1) *	L r = L r1 *

При запис регулярни изразище пропуснем знака за конкатенация и ще приемем, че операцията * има по-висок приоритет от конкатенацията и + , а конкатенацията има по-висок приоритет от + . Това ще позволи пропускането на много скоби. Например, може да се запише като 10(1 * + 0) .

Определение 5.1. две регулярни изрази r и p се наричат ​​еквивалентни, ако езиците, които представляват, съвпадат, т.е. L r = L p . В този случай пишем r = p.

Лесно се проверява напр. свойства на редоперации:

• r + p= p+ r (комутативен съюз),
• (r+p) +q = r + (p+q) (асоциативност на съюза),
• (r p) q = r (p q) (асоциативност на конкатенацията),
• (r *) * = r * (идемпотентност на итерация),
• (r+p) q = rq + pq(дистрибутивност).

Пример 5.1. Като пример, нека докажем не толкова очевидното равенство: (r + p) * = (r * p *) * .

Нека L 1 е езикът, представен от лявата му страна, а L 2 дясната страна. Празната дума принадлежи и на двата езика. Ако не е празна дума, тогава чрез дефиницията на итерация тя може да бъде представена като конкатенация на поддуми, принадлежащи на езика. Но този език е подмножество на езика L"=L r * L p * (защо?). Следователно . Обратно, ако една дума , тогава тя може да бъде представена като конкатенация на поддуми, принадлежащи на езика L". Всяка от тези поддуми v може да бъде представена като v= v 1 1 ... v k 1 v 1 2 ... v l 2, където за всички i=1, ... , k е поддума и за всички j=1, ... , l е поддума (възможно е k или l да е равно на 0). Но това означава, че w е конкатенация на поддуми, всяка от които принадлежи на и, следователно, .