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

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

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

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

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

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

Приклад:

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

d 0 → 0d1

d1 → 1d1

d1 → ε

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

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

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

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

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

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

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

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

d 0 → 00d0

d0 → ε

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

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

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

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

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

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

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

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

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

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

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

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

d0 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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,…} - як Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru ;

е) - {e, 0, 00, 000, } - як Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru ;

ж) {e, 000111, 000111000111, 000111000111000111,…} - як Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru ;

з) {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111,…} - як Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru .

Виникає таке враження, що довільна нескінченна множина, елементами якої є ланцюжки елементів 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) ei - регулярний вираз, що позначає регулярну множину {ei}, якщо ei Î Е;

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}*;

(e1 + e2) (e1 + e2 + e3 + e4) позначає множину слів з e1, e2, e3, e4, що розпочинаються на e1 чи e2.
Далі будемо позбавлятися від дужок, увівши пріоритет операцій. Розташуємо операції в порядку збільшення їх пріори­тет­у в такому порядку: ітерація; конкатенація; об'єднання. Домовимося, якщо при бездужковому записі декілька операцій претендують на виконання одночасно, першою будемо виконувати операцію з найменшим пріоритетом. У такий спосіб вираз Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru можна записати у вигляді Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru . Але вже вираз Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru без дужок без втрати значення записати не можна.

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

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

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

Визначення. Регулярні вирази 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. Але тоді, тому що Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru , то Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. - student2.ru .

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

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

Наши рекомендации