Материал: discrete_mathematics

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

Зв'язок наведених вище означень і понять установлює таке важливе твердження: будь-які ізоморфні автомати A1 і A2 є невідрізнюваними. Для його обґрунтування слід довести, що для будь-якого стану a автомата A1 стани a та γ(a) є невідрізнюваними, де γ – ізоморфізм автоматів A1 і A2.

У різних розділах математики в множині (класі) еквівалентних між собою об'єктів часто означають стандартних представників – канонічні, або нормальні, форми. Зведенням до канонічної форми можна перевірити (або встановити) еквівалентність або нееквівалентність певних об'єктів множини. Такою канонічною формою в теорії автоматів є мінімальний автомат.

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

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

1.Довести, що відношення невідрізнюваності є відношенням еквівалентності.

2.Побудувати приклад невідрізнюваних автоматів, які не ізоморфні.

5.4.Основні проблеми теорії автоматів

Стосовно зовнішніх умов функціонування розрізняють два типи поведінки і два відповідні типи скінченних автоматів.

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

Другий тип поведінки – це розпізнання певних множин вхід-

них слів. Автомат розпізнавач, або автомат акцептор, для

211

будь-якого вхідного слова 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