Обикновена дефиниция на езика е теорията на автоматите. Редовни езици и крайни автомати

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

Изявление

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

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

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

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

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

За да се конструира 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.Нека бъде 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 odedeе така:

съюз 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 odedeе така:

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

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

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

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

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

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

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

Нека 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; а * ааа *; ааа *; a * aa * aa * и т.н.

Определение 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 * a. Крайният автомат е специален случай на графа на преход и следователно всички езици, които са разрешени от автоматите, също са разрешени от графите за преход.

Теорема 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. Нека дефинираме такива автомати рекурсивно.

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

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

Лабораторна работа No3

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

Определение 1... генеративна граматика G = , чиито правила имат вида: A :: = aB или C :: = b, където A, B, C Є N; a, b Є Т се нарича редовен (автоматичен).

Езикът L (G), генериран от автоматна граматика, се нарича автоматен (обикновен) език или език с краен брой състояния.

Пример 1... Клас идентификатори, ако идентификаторът е поредица от букви и цифри и първият знак на идентификатора може да бъде само буква, се описва със следната генерираща редовна граматика G = , при което

N = (I, K), T = (b, q), S = (I),

P = (1.I :: = b

Тук b, c са обобщени терминални символи за букви и цифри, съответно.

Процесът на генериране на идентификатора "bbtsbts" се описва със следната последователност от замествания

I => bK => bbK => bbtsK => bbtsbK => bbtsbts

Основната задача на LA обаче не е генерирането на лексикални единици, а тяхното разпознаване. Математическият модел на обичайния процес на разпознаване на език е изчислително устройство, наречено краен автомат (CA). Терминът "ограничен" подчертава, че изчислителното устройство има фиксирано и ограничено количество памет и обработва поредица от входни знаци, принадлежащи на някакъв краен набор. Съществува Различни видове CA, ако изходната функция на CA (резултат от работата) е само индикация за това дали входната последователност от символи е допустима или не, такъв CA се нарича окончателен разпознавател.

Определение 2. Следните пет се наричат ​​краен автомат:

А = , където V = (a 1, a 2,…, a m) - входна азбука (краен набор от символи);

Q = (q 0, q 1,…, q n -1) - азбуката на състоянията (краен набор от символи);

δ: Q × V → Q е функцията на преход;

q 0 Є Q е началното състояние на крайния автомат;

F Є Q - набор от крайни състояния.

Схема на функциониране на SC.

Има безкрайна лента, разделена на клетки, всяка от които може да съдържа по един знак от V. Лентата съдържа верига α Є V *. Клетките отляво и отдясно на веригата са празни. Има крайно управляващо устройство (UU) с четяща глава, която може последователно да чете знаци от лентата, движейки се по лентата отляво надясно. В този случай CU може да бъде във всяко едно състояние от Q. CU винаги започва работата си в начално състояние q 0 и завършва в едно от крайните състояния F. Всеки път, преминавайки към нова клетка на лентата, CU преминава в ново състояние в съответствие с функцията δ.

Преходната функция на космическия кораб може да бъде представена по следните начини:

· Набор от екипи;

· Диаграма на състоянието;

· Преходна маса.

Командата на държавната машина се записва по следния начин:

(q i, a j) → q k, където q i, q k Є Q; a j Є V.

Тази команда означава, че състоянието на машината е в състояние q i, чете символа a j от лентата и преминава в състояние q k.

Графично командата е представена под формата на дъга на графика, минаваща от върха q i до върха q k и маркирана със символа a j на входната азбука:

Графичното представяне на цялото преобразуване δ се нарича диаграма на щатовата машина.

Ако космическият кораб се окаже в ситуация (q i, a j), която не е от лявата страна на никоя команда, тогава той спира. Ако UU преброи всички символи на низа α, записани на лентата, и в същото време премине в крайно състояние q r Є F, тогава се казва, че веригата α е допусната от краен автомат.

Таблицата на прехода на CA е конструирана по следния начин: колоните на матрицата съответстват на символи от входната азбука, редовете съответстват на символи от азбуката на състоянията, а елементите на матрицата съответстват на състоянията, в които преминава CA за дадена комбинация от входния символ и символа на състоянието.

Нека обикновена граматика G = , чиито правила са от вида: A i :: = a j A k или A i :: = a j, където A i, A k Є N и a j Є T.

Тогава крайният автомат A = допускайки същия език като този, генериран от обикновената граматика G, се конструира по следния начин:

2) Q = N U (Z), Z N и Z T, Z - крайното състояние на космическия кораб;

5) Отображението δ се конструира във вида:

· Всяко правило за заместване в граматиката G от вида А i :: = a j A k е свързано с командата (А i, a j) → A k;

· Всяко правило за заместване от вида А i :: = a j е свързано с командата (А i, a j) → Z;

Пример 2.Конструирайте CA за граматиката от пример 1. Имаме A = , където

1) V = T = (b, c)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: а) като набор от команди:

б) под формата на диаграма на състоянието

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

За практически цели е необходимо самият окончателен разпознавател да определи момента на края на входната последователност от знаци с издаване на съобщение за коректността или погрешността на входния низ. За тези цели входната верига се счита за ограничена отдясно от крайния маркер ├ и интерпретираните състояния се въвеждат в диаграмата на състоянието на SC:

Z - "допускане на входната верига";

О - "във входната верига е запазена грешка";

E - "отхвърляне на входното стъпало."

Състоянията Z и E са крайни и CA ги въвежда при четене на крайния маркер ├, съответно, след обработка на правилната или грешната входна верига. Състояние O е междинно, в него CA преминава от всяко допустимо състояние на CA, когато се открие грешка във входната верига и остава в него до пристигането на крайния маркер ├, след което се извършва преходът към състояние E - „отхвърляне входната верига”.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Израз r	Език L r
	L a = (a)
Нека r 1 и r 2 са	L r1 и L r2 са представителни
регулярни изрази.	тях езици.
След това следните изрази
са редовни	и представляват езици:
r = (r 1 + r 2)
r = (r 1 circr 2)
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 е конкатенация от поддуми, всяка от които принадлежи на и, следователно,.