Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини.

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

1. Загальна характеристика способів визначення мов. Найважливіша функція мови ко­му­нікативна. У процесі комунікації одна сторона формує мовне утворення, а інша сторона роз­пізнає його. Природними моделями для передавальної і приймаючої сторони є, відповід­но, процес (генератор), що породжує слова мови, і процес (пристрій), що розпізнає слова мо­ви. У першому випадку формальною моделлю визначення мови є граматика, а в другому – ав­то­мат. Генератори типу граматик для породження мов ми будемо вивчати в розділі 5, а авто­мати в ролі розпізнавачів – у розділі 4. У даній лекції ми коротко розглянемо сутність згаданих підходів, що дозволить глибше зрозуміти ідею ще одного підходу до визначення мов, побудованого на основі операційних моделей.

1.1. Граматики виникли в результаті спроби використовувати методи математики при дослідженні природних мов. Широке їхнє застосування в сфері інформатики, керування й обробки даних обумовлені ефективністю застосування граматик при розв’язанні лінгві­стич­­них проблем у згаданих сферах. Алгоритмічні мови звичайно визначаються гра­матиками.

Основна ідея граматик полягає в поступовому формуванні структури слів обумов­леної мови в спеціальних допоміжних символах алфавіту D з наступною заміною допоміж­них символів символами алфавіту E обумовленої мови.

Як процес формування структури слів обумовленої мови, так і процес заміни допо­між­них символів символами алфавіту обумовленої мови, виконуються шляхом застосування правил підстановки (виведення) вигляду α→β, де α,β - слова в алфавіті D U E. Якщо в гра­ма­тиці є правило підстановки α→β, то слово γ безпосередньо породжує слово δ, якщо γ = ωαh і δ= ωβh, де ω і h - довільні слова в алфавіті D U E. Рекурсія дозволить визначити породження словом γ слова δ. Залишається тільки визначити з чого розпочинається і чим закінчується процес пород­жен­ня. Для цього скористаємося поняттям початкового символу d₀ (слово d₀ приймаємо за спо­кон­віч­но породжене слово, з якого починається породження будь-якого слова обумовленої мови) і термінального слова, що містить тільки символи алфавіту E (процес породження, роз­по­чавшись зі слова d₀ закінчується тільки при породженні термінального слова). Обумовлена граматикою мова включає всі термінальні слова, породжувані даною граматикою з почат­кового символу d₀.

Приклад:

Граматика з алфавітами D = {d₀,d₁}, E = {0,1} і правилами:

d ₀ → 0d₁

d₁ → 1d₁

d₁ → ε

Тут 0 і 1 - термінальні символи, d₀ і d₁ не термінальні символи, причому d₀ – почат­ко­вий символ. Позначимо цю граматику G₁.

Тоді наступні послідовності слів в алфавіті пов'язані відношенням безпосереднього породження:

d ₀ (початковий символ), 0d₁ (тому що є правило підстановки d₀→0d₁), 0 (тому що є пра­вило підстановки d₁ → ε);

d ₀ (початковий символ), 0d₁ (тому що є правило підстановки d₀→0d₁), 01d₁ (тому що є правило підстановки d₁ → 1d₁), 01 (тому що є правило підстановки d₁ → ε);

d ₀ (початковий символ), 0d₁ (тому що є правило підстановки d₀→0d₁), 01d₁ (тому що є правило підстановки d₀→0d₁), 011d₁ (тому що є правило підстановки d₁ → 1d₁), 011 (тому що є правило підстановки d₁ → ε).

Звідси робимо висновок, що слова 0, 01, 011 – слова мови, обумовленої (пород­жува­ної) да­ною граматикою G₁. Очевидно, що всі слова мови, породжуваної даною граматикою, складуть множину {0, 01, 011, 0111, ...}.

Тепер спробуємо визначити граматикою мову {ε, 00,0000, 000000, ...}.

Для цього можна обійтися тільки одним допоміжним символом d₀ і правилами підстановки:

d ₀ → 00d₀

d₀ → ε

Тут 0 - термінальний символ, d₀ не термінальний символ, причому d₀ - початковий символ. Позначимо цю граматику G₂.

Тоді наступні послідовності слів в алфавіті пов'язані відношенням безпосереднього породження:

d₀ (початковий символ), ε (тому що є правило підстановки d₀→ ε);

d₀ (початковий символ), 00d₀ (тому що є правило підстановки d₀→00d₀), 00 (тому що є правило підстановки d₀→ ε);

d₀ (початковий символ), 00d₀ (тому що є правило підстановки d₀→00d₀), 0000d₀ (тому що є правило підстановки d₀→00d₀), 0000 (тому що є правило підстановки d₀→ ε);

d₀ (початковий символ), 00d₀ (тому що є правило підстановки d₀→00d₀), 0000d₀ (тому що є правило підстановки d₀→00d₀), 000000d₀ (тому що є правило підстановки d₀→00d₀), 000000 (тому що є правило підстановки d₀→ ε).

Звідси робимо висновок, що слова ε, 00, 0000, 000000 – слова мови, обумовленої (по­ро­д­­жу­­ва­­ної) даною граматикою G2. Очевидно, що всі слова мови, породжуваної даною граматикою складуть множину {ε, 00, 0000, 000000, ...}.

1.2. Автомати призначені для задання поведінки деяких систем, у першу чергу ком­п'ю­терів, шляхом визначення їхньої реакції (вихідного сигналу і наступного стану) на різні ситуації (комбінації вхідного сигналу і попереднього стану).

Основна ідея визначення мови автоматом складається в поступовому розпізнаванні структури слів мови, обумовленої автоматом, що переходить у визначені стани з появою тільки очікуваних символів і тільки в очікуваних станах.

При цьому зручно використовувати знайомі нам графічні засоби, що дозволяють ста­ни задати вершинами, а дозволені переходи – ребрами. Наприклад, нехай автомат заданий графом переходів:

0 d₁

d₀ 1

Тут d₀ і d₁ – стани, 0 і 1 – вхідні символи, перехід зі стану d₀ у стан d₁ здійснюється при вхідному символі 0 на вході автомата, а перехід зі стану d₁ у стан d₁ здійснюється при вхідному символі 1 на вході автомата.

Якщо прийняти, що автомат починає розпізнавати вхідну послідовність (послідов­ність вхідних символів), знаходячись у стані d₀ на момент подачі першого символу, а озна­кою розпізнавання вхідної послідовності як слова обумовленої мови є його перехід у стан d₁ по закінченні слова, то наведений автомат розпізнає наступні слова:

0 – знаходячись у стані d₀ автомат під впливом першого і єдиного символу цього слова перейде в стан d₁, що і буде ознакою розпізнавання;

01 - знаходячись у стані d₀ автомат під впливом першого символу цього слова перейде в стан d₁, а зі стану d₁ автомат під впливом другого й останнього символу цього слова перейде знову в стан d₁, що і буде ознакою розпізнавання;

011 - знаходячись у стані d₀ автомат під впливом першого символу цього слова перейде в стан d₁, зі стану d₁ автомат під впливом другого символу цього слова перейде знову в стан d₁, зі стану d₁ автомат під впливом третього й останнього символу цього слова перейде знову в стан d₁, що і буде ознакою розпізнавання.

Очевидно, що в такий же спосіб автомат розпізнає всі слова мови {0, 01, 011, 0111, ...}, визначеної вище за допомогою граматики G₁. Легко переконатися також, що автомат не розпізнає ніяких інших слів, крім слів мови {0, 01, 011, 0111, ...}. Таким чином, даний авто­мат визначає способом розпізнавання мову {0, 01, 011, 0111, ...}, визначену породженням за допомогою граматики G₁.

Важливість вибору стану, з якого автомат починає розпізнавання (початкового стану) і станів, що сигналізують про те, що переглянуте слово розпізнане (заключних станів) проде­монструємо на прикладі того ж автомата. Якби автомат знаходився в стані d₁ на момент по­да­чі першого символу, то вхідна послідовність, що вводиться, 01 не була б переглянута і, отже, розпізнана автоматом, тому що він не може реагувати в стані d₁ на вхідний символ 0. У цьому випадку він не може далі переглядати вхідне слово і, отже, не можна розглядати його стан d₁ як заключний тому що не завершений перегляд вхідного слова. З іншого боку, якщо автомат знаходиться в стані d₀ на момент подачі першого символу вхідної послідовності 010, то він не перегляне ланцюжок 010 і, хоча буде знаходитися в стані d₁ під впливом її підслова 01, це не буде ознакою розпізнавання, тому що вхідне слово не переглянуте.

Звідси, щоб однозначно визначити ті слова, що автоматом розпізнаються, необхідно:

1) чітко обумовити стан автомата, у якому він повинен починати перегляд вхідних програм (початковий стан);

2) обмовити стани, в один з яких повинен перейти автомат після закінчення вхідного слова (заключні стани).

Тепер визначимо автоматом мову {ε, 00, 0000, 000000,...}, визначену вище за допо­мо­гою граматики G₂. Граф переходів цього автомата має наступний вигляд:

d₀ d₁

Тут d₀ і d₁ – стани, 0 – вхідний символ, перехід зі стану d₀ у стан d₁ здійснюється при вхід­ному символі 0 на вході автомата, а перехід зі стану d₁ у стан d₀ здійснюється при вхід­ному символі 1 на вході автомата. Стан d₀ – початковий і заключний.

Наведений автомат розпізнає наступні слова:

ε – знаходячись у стані d₀, автомат знаходиться в заключному стані d₀, що і буде озна­кою розпізнавання, тому що вхідне слово не містить символи вхідної мови і, отже, уже переглянуте;

00 - знаходячись у стані d₀, автомат під впливом першого символу цього слова перей­де у стан d₁, а зі стану d₁ автомат під впливом другого й останнього символу цього слова перейде знову у стан d₀, що і буде ознакою розпізнавання;

0000 - знаходячись у стані d₀, автомат під впливом першого символу цього слова перейде у стан d₁, зі стану d₁ автомат під впливом другого символу цього слова перейде знову у стан d₀, зі стану d₀ автомат під впливом третього символу цього слова перейде знову у стан d₁, зі стану d₁ автомат під впливом четвертого й останнього символу цього слова перейде знову у стан d₀, що і буде ознакою розпізнавання.

Очевидно, що в такий же спосіб автомат розпізнає всі слова мови {ε, 00, 0000, 000000, ...}, визначеної вище за допомогою граматики G₂. Легко переконатися також, що автомат не розпізнає ніяких інших слів, крім слів мови {ε, 00, 0000, 000000,...}. Таким чином, даний авто­мат визначає способом розпізнавання мову {ε, 00, 0000, 000000,...}, визначену пород­жен­ням за допомогою граматики G₂.

1.3. Ідея операційного способу полягає у визначенні мови в алфавіті як результату вико­нання скінченого числа операцій над деякою початковою множиною «простих» мов. Звичайно під простими мовами маються на увазі мови, слова яких складаються не більш ніж з одного символу алфавіту. Цей спосіб розглянемо на прикладі важливого класу формальних мов.

2. Регулярні множини і вирази. Тепер уведемо формальні означення для того щоб уточнити викладене інтуїтивне уявлення про операційний спосіб.

Визначення. Визначимо регулярні множини в алфавіті Е в такий спосіб:

1) Æ – регулярна множина;

2) {e} - регулярна множина;

3) {e_i}, де e_i Î Е, - регулярна множина;

4) якщо R і S – регулярні множини в алфавіті Е, то R Ç S, RS, R* - також регулярні множини;

5) Т - регулярна множина в алфавіті Е тоді і тільки тоді, коли це випливає з пунктів 1) – 4) даного означення.

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

Приклади регулярних множин в алфавіті Е.

а) Æ

б) {e}; б') {0}; б”) {1};

в) {0,1} – як {0}È{1};

г) {00, 01, 10, 11} - як {0}{0}È{0}{1}È{1}{0}È{1}{1};

д) {e, 01, 0101, 010101,…} - як ;

е) - {e, 0, 00, 000, } - як ;

ж) {e, 000111, 000111000111, 000111000111000111,…} - як ;

з) {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111,…} - як .

Виникає таке враження, що довільна нескінченна множина, елементами якої є ланцюжки елементів 0,1 також є регулярною множиною. Однак, це не так. Розглянемо наступний

Приклад 1. Розглянемо нескінчену множину {e, 01, 0011, 000111,...}.

Ця множина не є регулярною. Зверніть увагу на те, що потрібен повтор однакової кількості 0 і 1, а ця побудова регулярної множини не забезпечується за скінчене число кроків. Дійсно, ми можемо, використовуючи конкатенацію, одержати будь-яке слово з однаковою кількістю 0 і 1, але тоді для нескінченної мови потрібно явно використовувати нескінченне число конкатенацій. Одна ітерація змогла б породити будь-яку послідовність однакових елементів або 0, або 1. Однак, ітерація дає довільне число елементів у слові і тому конкатенація двох ітерацій не забезпечить рівне число 0 і 1 у слові.

Аналогічно не є регулярними множини:

{011, 00111, 000011111,...};

{010, 001100, 000111000,...} і інші.

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

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

Визначення регулярних виразів:

1) Æ – регулярний вираз, що позначає регулярну множину Æ;

2) e - регулярннй вираз, що позначає регулярну множину {e};

3) e_i - регулярний вираз, що позначає регулярну множину {e_i}, якщо e_i Î Е;

4) якщо r і s - регулярні вирази, що позначають регулярні множини R і S, то (r + s), (rs), (r)* - регулярні вирази, що позначають відповідно регулярні множини R È S, RS, R*;

5) t – регулярний вираз тоді і тільки тоді, коли це є наслідком застосування пунктів 1) - 4) цього означення.

Приклад 2. Наведемо регулярні вирази для регулярних множин:

(01) позначає {01};

(010) позначає {010};

(0+1)* позначає {0,1}*;

(e₁ + e₂) (e₁ + e₂ + e₃ + e₄) позначає множину слів з e₁, e₂, e₃, e₄, що розпочинаються на e₁ чи e₂.
Далі будемо позбавлятися від дужок, увівши пріоритет операцій. Розташуємо операції в порядку збільшення їх пріори­тет­у в такому порядку: ітерація; конкатенація; об'єднання. Домовимося, якщо при бездужковому записі декілька операцій претендують на виконання одночасно, першою будемо виконувати операцію з найменшим пріоритетом. У такий спосіб вираз можна записати у вигляді . Але вже вираз без дужок без втрати значення записати не можна.

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

Тепер подивимося навпаки. Нехай регулярна множина містить слова e₁ і e₂, тобто R = {e₁} È {e₂}. Регулярний вираз, що позначає її, має вигляд (e₁ + e₂). Але і (e₂ + e₁) також позначає ту ж множину. Чи розглянемо множину слів довільної довжини із символів e₁ і e₂, тобто регулярну множину ({e₁} È {e₂})*. Її також позначають (e₁ + e₂)* чи (e₂ + e₁)*. Таким чином, для кожної регулярної множини може існувати множина регулярних виразів, що позначають її .

На множинах природно визначається відношення рівності. Скористаємося цим і визначимо відношення рівності регулярних виразів.

Визначення. Регулярні вирази r і s рівні (будемо позначати цей факт r = s), якщо вони позначають рівні множини.

Природно, що ми використовуємо уже введене нами раніше визначення рівних множин.

Теорема 5. Якщо r, s, t – регулярні вирази, то справедливі такі рівності:

r + s = s + r ;

r +(s + t) = (r + s) + t , r(st) = (rs)t;

r (s + t) = rs + st , (s + t)r = sr + tr;

re = e r= r ;

r* = r + r*;

r + r = r ;

(r*)* = r*;

Æ*= e;

Ær = rÆ = Æ;

r + Æ = r .

Доведення. Нехай r позначає регулярну множину R, а s - регулярну множину S. Але тоді, тому що , то .

Аналогічно доводяться інші рівності. Теорема доведена.

3. Регулярні множини і мови. За означенням регулярна множина – мова. Пізніше ми покажемо, що регулярні множини визначають важливий клас формальних мов, що називаються також регулярними.