Регулярні мови та кінцеві автомати. Регулярна мова Регулярні мови та кінцеві автомати

Регулярні множинита регулярні вирази

Регулярні множини

У цьому розділі ми розглянемо клас множин ланцюжків над кінцевим словником, які дуже легко описати формулами певного виду. Ці множини називаються регулярними.

Визначення 1.Нехай V 1 і V 2 - безлічі ланцюжків. Визначимо три операціїна цих множинах.

Об'єднання: V 1 V 2 =(|   V 1 ) або   V 2 .

Конкатенація (твір, склеювання): Vl  V2 = (|  V 1 ,  V 2 ) Знак операції конкатенації зазвичай опускається.

Приклад: V, = (abc, ba), V2 = (b, cb). V1V2 = (abcb, abccb, bab, bacb).

Позначимо V n добуток n множин V:V n =VV...V,V° =() (тут -порожній ланцюжок).

Приклад: V1 = (abc, ba), V12 = (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* та Т*.

5. Якщо безліч може бути побудовано кінцевим числом застосування правил 1-4, воно нерегулярно.

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

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

Регулярні множини хороші тим, що їх можна дуже просто описати формулами, які ми назвемо регулярними виразами.

Визначення 2.Клас регулярних виразів над кінцевим словником V визнайтеється так:

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

їх добуток R1R2;

їх ітерація R1 і R2.

4. Якщо вираз не побудовано кінцевим числом застосування правил 1-3, воно не є регулярним.

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

Приклади регулярних виразів: ab+ba*; (аа) * b + (з + dab) *.

Вочевидь, що регулярні множини і регулярні висловлювання дуже близькі. Але вони являють собою різні сутності: регулярне безліч - це безліч ланцюжків (загалом нескінченне), а регулярний вираз - цеформула, схематично показує, як було побудовано відповідне їй регулярне безліч за допомогою перерахованих вище операцій(і ця формула є кінцевою).

Нехай R^ - регулярна множина, що відповідає регулярному виразу R. Тоді:

Таким чином, регулярне вираз - це кінцева формула, що задає безліч ланцюжків, тобто мову.

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

Регулярний вираз	Відповідна мова
	Усі ланцюжки, що починаються з b, за яким слідує довільна кількість символів а
	Всі ланцюжки а і b, що містять рівно два входження b
	Всі ланцюжки з а і b, до яких символи входять лише парами
(a+b)*(aa+bb)(a+b)*	Всі ланцюжки з а і b, що містять хоча б одну пару, що поряд стоять а або b
(0+1)*11001(0+1)*	Усі ланцюжки з 0 і 1, що містять підчіпку 11001
	Усі ланцюжки з а та b, що починаються символом а та закінчуються символом b

Очевидно, що безліч ланцюжків регулярно тоді і тільки тоді, коли вона може бути представлена ​​регулярним виразом. Однак те саме безліч ланцюжків може бути представлено різними регулярними виразами, наприклад, безліч ланцюжків, що складається з символів а і містить не менше двох а може бути представлено виразами: аа * а; а*ааа*; ааа*; а*аа*аа* і т.д.

Визначення 3.Два регулярні вирази R1 і R2 називаються еквівалентними (позначається Rl = R2) тоді і лише тоді, колиR1 ^ = R2 ^ .

Отже, аа*а = а*ааа* = ааа* = а*аа*аа*. Виникає питання, як визначити еквівалентність двох регулярних виразів.

Теорема1 . Для будь-яких регулярних виразів R, S іТ справедливо:

Ці співвідношення можна довести, перевіряючи рівність відповідних множин ланцюжків. Їх можна використовувати для спрощення регулярних виразів. Наприклад: b (b + aa * b) = b (b + aa * b) = b (b + aa *) b = ba * b. Звідси b (b + aa * b) = ba * b, що очевидно.

Теорема Кліні

Регулярні вирази – це кінцеві формули, що задають регулярні мови. Але таку ж властивість мають і кінцеві автомати - вони теж задають мови. Виникає питання: як співвідносяться між собою класи мов, що задаються кінцевими автоматами та регулярними виразами? Позначимо А безліч автоматних мов, R – безліч регулярних мов. Стефен Кліні, американський математик, довів таку теорему.

Теорема2 . (Теорема Кліні.) Класи регулярних множин та автоматних мов збігаються, тобто А = R .

Іншими словами, кожна автоматна мова може бути задана формулою (регулярним виразом) і кожна регулярна множина може бути розпізнана кінцевим автоматом. Ми доведемо цю теорему конструктивно, за два кроки. На першому кроці доведемо, що будь-яка автоматна мова є регулярною безліччю (або, що те саме, для будь-якого кінцевого автомата можна побудувати регулярне вираз, що задає мову, що розпізнається цим автоматом). На другому кроці доведемо, що будь-яка регулярна множина є автоматною мовою (або, що те саме, за будь-яким регулярним виразом можна побудувати кінцевий автомат, що допускає в точності ланцюжка відповідної регулярної множини).

Введемо на розгляд модель графа переходів як узагальнення моделі кінцевого автомата. У графі переходів одна початкова і довільна кількість заключних вершин, а спрямовані ребра позначені, на відміну кінцевого автомата, не символами, а регулярними висловлюваннями. Граф переходів допускає ланцюжок а, якщо аналежить безлічі ланцюжків, що описується добутком регулярних виразів R 1 R 2 ...R n , Які позначають шлях з початкової вершини в одну із заключних вершин. Безліч ланцюжків, що допускаються графом переходів, утворює мова, що допускається ним.

Рис. 1. Граф переходів

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

Теорема 3.Кожна автоматна мова є регулярним безліччю, А  R.

Доведення. Граф переходів з однією початковою та однією заключною вершинами, у якого єдине ребро з початкової в заключну вершину позначено регулярним виразом R, допускає мову R^ (рис. 1).

Рис. 2. Граф переходів, що припускає регулярну мову FT

Доведемо тепер, що кожна автоматна мова є регулярним безліччю приведенням будь-якого графа переходів без зміни мови до еквівалентного виду (рис. 2).

Будь-який кінцевий автомат і будь-який граф переходів завжди можна уявити в нормалізованій формі, в якій тільки одна початкова вершина тільки з вихідними ребрами і тільки одна заключна вершина тільки з ребрами, що входять (рис. 3).

Рис. 3. Граф переходів з однією початковою та однією заключною вершинами

З графом переходів, представленим у нормалізованій формі, можуть бути виконані дві операції редукції - редукція ребра та редукція вершини - зі збереженням допустимої цим графом переходів мови:

а) редукція ребра:

Б ) редукція вершини (заміна виконується для кожного шляху, що проходить через вершину р, з подальшим її викиданням як недосяжний стан):

Вочевидь, кожна операція редукції не змінює мови, розпізнаваного графом переходів, але зменшує чи кількість ребер, чи кількість вершин, і зрештою редукції приведуть граф переходів до виду, наведеному на рис. 2. Теорема доведена: кожна автоматна мова є регулярною безліччю.

приклад

Нехай заданий кінцевий автомат А:

Будуємо еквівалентний граф переходів у нормалізованому вигляді.

Редукція вершини 3:

Редукція дуг та застосування правила R = R:

Редукція вершини 2:

Редукція дуги та вершини 1:

Таким чином, мова, що розпізнається автоматом А, задається регулярним виразом: RA = b+(a+bb)(b+ab)*a.

Доведемо теорему Кліні в інший бік.

Теорема 2.Кожна регулярна множина є автоматною мовою: R  A.

Доведення.Покажемо, що для кожного регулярного виразу R може бути побудований кінцевий автомат A r (можливо недетермінований), що розпізнає мову, що задається R. Визначення таких автоматів дамо рекурсивно.

(Початковий та заключний стан А поєднуються).

приклад(продовження)

Регулярні граматики, кінцеві автомати та регулярні множини (і позначають їх регулярні вирази) є три різних способи завдання регулярних мов.

Твердження

Мова є РМ тоді і тільки тоді, коли вона задана ліволінійною (праволінійною) граматикою. Мова може бути задана леволінійною (праволінійною) граматикою тоді і тільки тоді, коли вона є регулярною множиною.

Мова є РМ тоді і лише тоді, коли він заданий за допомогою кінцевого автомата. Мова розпізнається за допомогою кінцевого автомата тоді і лише тоді, коли він є РМ.

Усі ці три способи еквівалентні. Існують алгоритми, що дозволяють для мови, заданого одним із зазначених способів, побудувати інший спосіб, що визначає ту саму мову. Детальний опис цих алгоритмів є у літературі (див. список).

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

Теоретично мов програмування найважливішу роль грає еквівалентність КА і регулярних граматик, оскільки такі граматики використовуються визначення лексичних конструкцій мов програмування. Створивши на основі відомої граматики автомат, отримуємо розпізнавач для цієї мови. Таким чином, вдається вирішити завдання розбору для лексичних конструкцій мови.

Для побудови КА на основі відомої регулярної граматики необхідно привести до автоматного вигляду. Безліч станів автомата буде відповідати безлічі символів нетермінальних граматики. 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. Початкові поняття теорії формальних мов

Розглянемо непусту кінцеву множину А, що складається із символів ( a 1 , …, a k). Будемо називати А алфавітом , а його символи – літерами . Будь-яка кінцева послідовність літер цього алфавіту називається словом (ланцюжком або рядком ): w=a 1 a 2 …a n- Слово ( a i A), |w| - Довжина слова (число букв, з яких складається слово, причому кожен символ зустрічається стільки разів, скільки разів він зустрічається в w). Через | w| bпозначимо кількість входжень символу bу слово w.

Нескінченна послідовність букв алфавіту Аназивається надсловом , - надслово з нескінченного числа букв а. Порожнім називається слово, що не містить жодної літери. Воно позначається через . Вочевидь, ||=0.

- безліч слів алфавіту Адовжини n. Безліч всіх слів алфавіту А(включаючи надслова) позначається А*. Це безліч лічильне, оскільки є об'єднанням лічильного числа кінцевих множин
. Безліч пустих слів в алфавіті Апозначається А+. Якщо A={a), то А*={a)* будемо позначати через а*.

Будь-яке підмножина
називається мовою (формальною мовою ) над алфавітом А.

Якщо xі y- Слова мови
, то слово ху(Результат приписування слова унаприкінці слова х) називається конкатенацією (зчепленням , твором ) слів хі у.
(nраз беремо х). Покладемо
.

Говорять, що слово х – підслів слова у, якщо y=uxvдля деяких слів uі v. Усі підслівні слова мови
утворюють безліч підслів мови L, Що позначається через Subw( L).

Приклади. 1. ba 3 =baaa,
- у цьому слові є підслів ab, aba, baі т.п.

2. Безліч ( a, abb) - мова (кінцева) над алфавітом ( a, b}.

3. Безліч
є мовою над алфавітом ( a, b). Ця мова нескінченна, вона містить слова b, ba, aba, baa, abaa, baaa, aabaa, abaaaі т.д.

Оскільки кожна мова є безліччю, можна розглядати операції об'єднання, перетину та різниці мов, заданих над тим самим алфавітом. Так, мова
, де
, називається доповненням мови Lщодо алфавіту А. І якщо  завжди включено до А*, то мова
може як утримувати, так і не утримувати його. В останньому випадку
.

Нехай ,
. Тоді мова називається конкатенацією (зчепленням , твором ) мов і . При цьому
,
(nраз), якщо n>0.

Приклади. 1. Якщо
,
,то .

2. Якщо L = (0, 01), то
.

Ітерацією мови Lназивається мова
(Ця операція називається також зірочкою Кліні ). Мова
називається позитивною ітерацією мови L.

приклад. Якщо A={a, b) та L={aa, ab, ba, bb), то
.

Зверненням або дзеркальним чином слова wназивається слово w R, в якому букви слова wйдуть у зворотному порядку. Наприклад, якщо w=bac, то

Нехай
. Тоді мова
називається зверненням мови L.

Будь-який початок слова будемо називати префіксом , а всякий кінець слова – суфіксом . Наприклад, якщо y=xv, то х- Префікс слова у(позначення – х[y), а v- Суфікс слова у(позначення – v]y). Очевидно, що порожнє слово є префіксом, так і суфіксом будь-якого слова. Усі префікси слів мови
формують безліч префіксів цієї мови: Pref( L)
. АналогічноSuf( L)
-м ножство суфіксів мови
.

Якщо мова Lтакий, що жодне слово Lне є префіксом (суфіксом) жодного іншого слова L, то кажуть, що Lмає префіксним (Суфіксним) властивістю .

Нехай А 1 та А 2 – алфавіти. Якщо відображення f:
задовольняє умову всім слів
і
, то відображення fназивається гомоморфізмом .

Зауваження. 1. Можна довести, що якщо f- гомоморфізм, то
.

2. Гомоморфізми який завжди є биекциями, але кожен гомоморфізм однозначно визначається своїми значеннями на однобуквенных словах.

3. Застосовуючи гомоморфізм до мови L, отримуємо іншу мову f(L).

Якщо f:
- Гомоморфізм,
і
, то через f(L 1) позначається мова
, а через
позначається мова
, а саме відображення
називається зверненням гомоморфізму .

Приклади. 1. Допустимо, ми хочемо замінити кожне входження в ланцюжок символу 0 на символ а, а кожне входження 1 – на bb. Тоді можна визначити гомоморфізм fтак що
і
. Якщо
, то
.

2. Нехай f– гомоморфізм, для якого
і
. Тоді
і
.

У цьому розділі ми починаємо викладення елементів теорії формальних мов.

Говорячи " формальний мову " , маємо у вигляді те, що наведені тут результати використовуються передусім описі штучних мов, придуманих людьми для спеціальних цілей, наприклад мов програмування. Але непереборної перешкоди між спеціально придуманими штучними (формальними) мовами і природними мовами, що стихійно виникають і розвиваються, не існує. Виявляється, що природні мови характеризуються складними граматичними правилами, тобто. досить жорстко формалізовані, а навіть "науково розроблена" мова програмування містить "темні місця", однозначне розуміння яких є проблемою.

Вивчаючи мови, слід мати на увазі три основні аспекти.

Перший з них - синтаксис мови . Мова - це якась безліч "слів", де "слово" є певна кінцева послідовність "літер" - символів якогось заздалегідь фіксованого алфавіту. Терміни "літера" та "слово" можуть розумітися по-різному (математичне визначення цих термінів буде дано нижче). Так, "літерами" можуть бути дійсно літери алфавіту якоїсь природної або формальної мови, наприклад російської мови або програмування "Паскаль". Тоді "словами" будуть кінцеві послідовності "літер": крокодил", " integer". Такі слова називають "лексемами". Але "літерою" може бути "слово" ("лексема") в цілому. Тоді "слова" - це пропозиції природної мови або програми мови програмування. Якщо фіксована якась безліч "літер", то не кожна їхня послідовність буде "словом", тобто Елексемою даної мови, а тільки така послідовність, яка підпорядковується певним правилам. Слово "крикаділ" не є лексемою російської мови, а слово "iff" не є лексемою в "Паскалі". Пропозиція "Я люблю ти" не є правильною пропозицією російської мови, так само, як і запис "х:= =t" не є правильно написаний оператор присвоювання "Паскаля". Синтаксис* мови і є системою правил, відповідно до якими можна будувати "правильні" послідовності "літер". Кожне слово мови характеризується певною структурою, специфічною саме цієї мови. Тоді необхідно, з одного боку, розробити механізми перерахування, або породження, слів із заданою структурою, а з іншого - механізми перевірки того, що це слово належить цій мові. Насамперед саме: ці механізми і вивчає класична теорія формальних мов.

Другий аспект - семантика мови . Семантика** передбачає зіставлення словами мови якогось "сенсу", Езначення". Наприклад, записуючи математичну формулу, ми повинні дотримуватися певних синтаксичних правил (розстановка дужок, правопис символів, порядок символів і т.п.), але, крім цього, формула має цілком певний сенс щось позначає.

Мова – це засіб спілкування, передачі інформації. Якщо ми хочемо, щоб нас зрозуміли, ми повинні не тільки синтаксично правильно, дотримуючись належного порядку букв у слові та слів у реченні, будувати свою мову, а й дбати про її зміст, про ті ідеї, які ми висловлюємо у мові. Математичні теорії "сенсу" з'явилися порівняно недавно, і на додаток до наступного розділу ми дуже коротко розглянемо деякі підходи до математичного опису семантики мов програмування.

* Слово "синтаксис" походить від давньогрецьких "syn" - "разом" та "taxis" - "порядок, лад". Таким чином, синтаксис можна розуміти як "складання".

** Від давньогрецьких слів "sema" - "знак, знак" і "semanticos" - "що позначає".

Нарешті, третій аспект - прагматика мови . Прагматика пов'язана з тими цілями, які ставить перед собою носій мови: наприклад, людина вимовляє мову, маючи перед собою цілі, пов'язані не з синтаксисом, не з семантикою мови, якою вона говорить або пише, а, скажімо, з отриманням за певну мову суми грошей. Прагматика є вже скоріше дисципліною соціально-філософської, що зачіпає цілу діяльність особистості. Ми ні в якому разі не будемо її торкатися.

У цьому розділі спочатку будуть розглянуті основні поняття математичної теорії формальних мов, найважливішим серед яких є поняття граматики, що породжує, а за тим - так звані регулярні мови. Теорія регулярних мов разом із теорією кінцевих автоматів утворює фундамент всієї теорії формальних мов.

• Алфавіт, слово, мова

• Граматики, що породжують

  Як зазначалося, класична теорія формальних мов вивчає передусім синтаксис мови. Вона вводить математичну модель синтаксису, яка описує механізми породження та розпізнавання "правильно побудованих" ланцюжків. У цьому розділі ми розглянемо перший із цих механізмів.

операції об'єднання мов ми знаємо. Визначимо операції конкатенації та ітерації (іноді її називають замиканням Клині).

Нехай 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 є конкатенацією підслів, кожне з яких належить і, отже, .