Ноу Інти, лекція, регулярні мови і кінцеві автомати

Анотація: Операції конкатенації і ітерації мов. Регулярні вирази і мови. Приклади регулярних виразів і мов. Побудова кінцевого автомата по регулярному виразу

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

Регулярні вирази є досить зручним засобом для побудови "алгебраїчних" описів мов. Вони будуються з елементарних виразів за допомогою операцій об'єднання (+), конкатенації () і ітерації (*). Кожному такому вираженню r відповідає представляється їм мову Lr. Сенс операції об'єднання мов ми знаємо. Визначимо операції конкатенації і ітерації (іноді її називають замиканням Кліні).

Нехай L1 і L2 - мови в алфавіті

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

Введемо позначення для "ступенів" мови L:

Таким чином в L i входять всі слова, які можна розбити на i поспіль слів з L.

Ітерацію (L) * мови L утворюють всі слова які можна розбити на кілька поспіль слів з L:

Її можна представити за допомогою ступенів:

Часто зручно розглядати "усічену" ітерацію мови, яка не містить пусте слово. якщо його немає в мові:. Це не нова операція, а просто зручне скорочення для вираження.

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

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

При записи регулярних виразів будемо опускати знак конкатенації і будемо вважати, що операція * має більший пріоритет, ніж конкатенація і +. а конкатенація - більший пріоритет, ніж +. Це дозволить опустити багато дужки. Наприклад, можна записати як 10 (1 * + 0).

Визначення 5.1. Два регулярних вирази r і p називаються еквівалентними, якщо збігаються подаються ними мови, тобто Lr = Lp. В цьому випадку пишемо 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 *) *.

Нехай L1 - мова, що представляється його лівою частиною, а L2 - правою. Пусте слово належить обом мовам. Якщо непорожнє слово, то за визначенням ітерації воно представимо як конкатенація Підшар, що належать мови. Але ця мова є підмножиною мови L '= Lr * Lp * (чому?). Тому. Назад, якщо слово, то воно представимо як конкатенація Підшар, що належать мови L '. Кожне з таких Підшар v представимо у вигляді v = v1 1. vk 1 v1 2. vl 2. де для всіх i = 1. k подсловом і для всіх j = 1. l подсловом (можливо, що k або l дорівнює 0). Але це означає, що w є конкатенацией Підшар, кожне з яких належить і, отже,.

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

Приклад 5.2. Регулярний вираз (0 +1) * представляє безліч всіх слів в алфавіті.

Приклад 5.3. Регулярний вираз 11 (0 +1) * 001 представляє мову, що складається з усіх слів в алфавіті. які починаються на '11', а закінчуються на '001'.

Приклад 5.4. Регулярний вираз являє мову, що складається з усіх слів в алфавіті. які не містять подсловом '000' (див. задачу 5.3).

Приклад 5.5. Регулярний вираз 1 * (01 * 01 *) * представляє мову L0ч. що складається з усіх слів в алфавіті. в яких парне число нулів.

Дійсно, кожне слово з L0ч або взагалі не містить нулів, тобто входить в мову, що представляє 1 *. або може бути розбите на блоки виду 01 i 01 j. i, j> = 0. яким, можливо, передує блок одиниць. Вираз (01 * 01 *). очевидно задає один такий блок, а його ітерація - довільну послідовність таких блоків.

Приклад 5.6. Побудуємо тепер регулярний вираз. що представляє мову L0ч1ч. який складається з усіх слів в алфавіті. містять парне число нулів і парне число одиниць.

Нехай w = w1 w2. wn - довільне слово з L0ч1ч. Тоді, зрозуміло, n - парне, нехай n = 2k. Розіб'ємо w на пари сусідніх букв pi = w2i-1 w2i. i = 1,2. k. Можливі 4 види таких пар: 00, 11, 01 і 10. Пар виду 00 і 11 може бути скільки завгодно, а пар виду 01 і 10 обов'язково парне число. Тому w розбивається на блоки, кожен з яких починається однією з пар 01 або 10 і містить ще одну таку пару. Кожен такий блок описується виразом (01 +10) (00 + 11) * (01 + 10) (00 + 11) *. При цьому перед першим блоком може бути префікс. що складається з пар 00 і 11. Безліч слів складаються з пар 00 і 11 задається виразом (00 +11) *. Звідси отримуємо вираз R0ч1ч. задає мову L0ч1ч: