Материал: discrete_mathematics

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

Найпоширенішу модель ініціального автомата-розпізнавача A = (X, Y, U, δ, λ) означають так. Множину станів U розбивають на дві підмножини: U1 та U2. Вважають, що слово p X* розпізнається автоматом A, якщо δ(a1, p) U1; в іншому разі (δ(a1, p) U2) слово p відкидається.

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

Основними проблемами теорії автоматів для кожного з типів поведінкийтипівавтоматіввважаютьпроблемианалізутасинтезу.

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

У задачі синтезу потрібно, виходячи із заданих умов поведінки, побудувати (синтезувати) автомат, що реалізує цю поведінку. Очевидно, що одна з перших проблем, яка виникає при роз- в'язанні задачі синтезу – це дослідження питання, які з умов поведінки взагалі можуть бути реалізовані у автоматах, зокрема у скінченних автоматах. Відтак постає проблема побудови власне алгоритму синтезу.

212

5.5. Зображення подій у автоматах

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

Автомат без виходів A = (X, U, δ, a1, F) означають так: перші три об'єкти X, U і δ мають той самий зміст, що й раніше, a1 U – початковий стан, F – множина заключних станів автомата A, F U. У найближчих параграфах будемо розглядати без додаткових застережень ініціальні скінченні автомати без виходів.

Множину P слів у вхідному алфавіті X, тобто P X*, називатимемо подією в алфавіті X.

Цей термін став традиційним у теорії автоматів, хоча він не містить нічого принципово нового: можна було б користуватися просто терміном множина слів у алфавіті X. Інший термін для цього самого поняття – мова.

Подія P зображувана в автоматі A = (X, U, δ, a1, F) (або ав-

томат A зображує подію P), якщо δ(a1, w) F, тоді й тільки тоді, коли w P.

Кожному автомату A = (X, U, δ, a1, F) відповідає зображувана в ньому подія P. Подію P зручно проілюструвати за допомогою графа автомата A: подія P складається зі всіх вхідних слів, відповідні шляхи яких у графі автомата A ведуть із вершини a1 у вершини з множини F.

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

жина, або мова, яка визначає, допускає чи розпізнає автомат.

Можлива ситуація, коли a1 F. У цьому разі вважатимемо, що події P, зображуваній у автоматі A, належить порожнє слово e. Порожнє слово не слід плутати з порожньою подією. Автомат A зображує порожню подію, якщо не існує жодного вхідного слова, яке переводить автомат A з початкового стану a1 в будь-який

213

із заключних станів. Порожню подію будемо позначати символом порожньої множини .

Будь-яка скінченна множина слів P = {w1, w2, …, wk} в алфавіті X (скінченна подія) зображувана в скінченному автоматі.

Приклад 5.3.

1. На рис. 5.4 подано граф автомата A, що зображує скінченну

подію P = {x1x2x1x1, x1x1x2, x1x1x1x2, x1x1x1}. Нижче виписано всі підслова слів множини P і відповідні до них стани шуканого

автомата A. Заключні стани автомата A позначено подвійними кругами (кожен з них відповідає одному зі слів події P).

e – a1, x1 – a2, x1x1 – a3, x1x2 – a4, x1x1x1 – a5, x1x1x2 – a6, x1x2x1 – a7, x1x1x1x2 – a8, x1x2x1x1 – a9.

2. Побудувати автомат-розпізнавач, який зображує подію в алфавіті B = {0, 1}, що складається зі всіх слів, які починаються з 00 і закінчуються парою символів 11, тобто мають вигляд

00w11, w B*.

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

3. Побудувати скінченний автомат для розпізнавання, чи є вхідний набір символівідентифікатором якоїсьмови програмування.

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

214

Завдання для самостійної роботи

1. Побудувати автомат-розпізнавач, що зображує скінченну подію P:

(а) P = {x1x1x1x2, x1x1x2x2x1, x1x1x1x1x2, x1x1x1x2x1x1}; (б) P = {e, x1x2x1x1x2x2, x1x1x2x1x1x2, x1x2x1x1}.

2.Нехай подія P зображувана в скінченному автоматі A та e P. Як побудувати новий скінченний автомат A′, що зображує подію P {e}?

3.Побудувати автомат-розпізнавач, який зображує подію в алфавіті B = {0, 1}, що складається зі всіх слів, які починаються

йзакінчуються парами символів 00 або 11, тобто мають вигляд

00w00 або 11p11, w, p B*.

4. Побудувати скінченний автомат для розпізнавання певної синтаксичної конструкції:

(а) число з фіксованою крапкою; (б) простий арифметичний вираз; (в) коментарі.

5.6.Алгебра регулярних подій

Упопередньому параграфі ми навели приклад класу подій – клас скінченних подій, які завжди зображувані в скінченних автоматах. Однак існують події, незображувані в скінченних автоматах. Зрозуміло, що в скінченних автоматах зображувані не тільки скінченні події. Бажано було б мати засоби, за допомогою яких можна було б описувати події, зображувані в скінченних автоматах. Один із таких засобів, запропонований С.-К. Кліні, розвинутий і вдосконалений В. М. Глушковим, Р. Ф. Мак-Ното-

ном та іншими, має назву мови регулярних виразiв.

215

Нехай P1, P2 X* – події в алфавіті X. Розглянемо три операції над подіями, які називатимемо регулярними операціями.

1.Об'єднання (іноді диз'юнкція) подій P1 P2 – це звичайне теоретико-множинне об'єднання.

2.Множення (конкатенація) подій P1P2 – це подія, яка скла-

дається зі всіх таких слів w1w2, що w1 P1 і w2 P2. Зазвичай операцію множення подій використовують без спеціального позначення. Для зручності посилання на цю операцію позначатимемо

їїчерез .

3.Ітерацією події P називають подію

P* = {e} P P2 ... Pn ... = ∞ Pn .

n=0

Тут через P0 позначено подію {e}, а через Pn – подію PP…P (n разів). Іноді операцію ітерації події P позначають {P}.

Звернемо увагу на те, що введене вище позначення X* для множини всіх слів у алфавіті

X= {x1, x2, …, xm}

іпозначення X* операції ітерації для події X мають той самий

смисл. Дійсно, подія

X* = ({x1} {x2} … {xm})*

складається зі всіх слів (включаючи порожнє слово) в алфавіті X. Через P + позначатимемо подію P*\{e}.

Окремо зазначимо деякі важливі події. Подію, яка містить усі слова в алфавіті X, тобто X*, назвемо загальною. Подію, яка не містить жодного слова, назвемо порожньою, або неможливою й позначимо символом порожньої множини .

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

Приклад 5.4.

1. Виписати всі слова події P* в алфавіті X = {a, b}, довжина