4.7.5. Скінченні автомати

Скінченні автомати можна розглядати як обмежені машини Тьюрінга, що мають одну вхідну стрічку – голівка може тільки читати символи і рухатися тільки в один бік. Тому такі автомати не мають необмеженої пам’яті. Екстенсіональне визначення наступне.

Визначення 4.30. Скінченний автомат – це п’ятірка M =(Q, A, , q₀, F), де

• Q – скінченна множина станів,

• A – скінченний вхідний алфавіт (QA=),

•  – скінченне відношення переходів (скінченне відображення :QAQ),

• q ₀ – початковий стан із Q,

• F – підмножина фінальних (заключних) станів із Q.

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

Основним є наступний результат.

Теорема 4.7. За кожним скінченним автоматом можна побудувати еквівалентну йому породжуючу граматику типу 3 (ліволінійну чи праволінійну граматику), і навпаки, за кожною породжуючою граматикою типу 3 можна побудувати еквівалентний їй скінченний автомат.

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

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

Регулярні мови задаються виразами (термами) регулярної алгебри мов, що має операції об’єднання, конкатенації та ітерації.

Регулярні вирази можна визначити індуктивно.

Базис складається з трьох визначень.

1. Константи ε та Ø є регулярними виразами.

2. Якщо a – довільний символ алфавіту, то a – регулярний вираз. Зауважимо, що часто в написанні розрізняють символ алфавіту та відповідний вираз. Тут це не робимо, щоб не ускладнювати текст.

3. Якщо X – змінна, то X – регулярний вираз.

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

1. Якщо E та F – регулярні вирази, то E+F – регулярний вираз.

2. Якщо E та F – регулярні вирази, то EF – регулярний вираз. Зауважимо, що для позначення оператора конкатенації – як операції над мовами, так і оператора в регулярному виразі – можна використовувати крапку.

3. Якщо Е – регулярний вираз, то Е* – регулярний вираз.

4. Якщо Е – регулярний вираз, то (Е) – регулярний вираз.

Інтерпретація L виразів у класі мов над алфавітом A задається також індуктивно на підставі інтерпретації змінних L_V: Var 2^A*, де Var – множина змінних.

Інтерпретація базових виразів задається таким чином:

1. L(ε) = {ε} і L(Ø) = Ø.

2. L(a) = {a}.

3. L(X) = L_V(X).

Інтерпретація складних виразів задається таким чином (E та F – регулярні вирази):

1. L(E+F) = L(E) L(F).

2. L(EF) = L(E)L(F).

3. L(E*) = (L(E))* .

4. L((E)) = L(E).

Ми використовуємо L(E) для позначення мови, яка відповідає Е. Як і в інших алгебрах, оператори регулярних виразів мають певні пріоритети, тобто оператори зв’язуються зі своїми операндами в певному порядку.

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

Основний результат стосовно регулярних мов є наступний.

Теорема 4.8. За кожним скінченним автоматом можна побудувати еквівалентний йому регулярний вираз, і навпаки, за кожним регулярним виразом можна побудувати еквівалентний йому скінченний автомат.

Наведений результат дозволяє використовувати різні формалізми (граматики типу 3, скінченні автомати, регулярні вирази) для дослідження властивостей регулярних мов. Такі мови мають гарні властивості замкненості (відносно об’єднань, перетину, доповнень, конкатенації, ітерації та деяких інших операцій). Ще одну важливу групу властивостей регулярних мов становлять «властивості розв’язності». За їх допомогою можна з’ясувати, чи визначають два різні автомати одну і ту саму мову. Розв’язність цієї задачі дозволяє мінімізувати автомати, тобто за даним автоматом знайти еквівалентний йому з найменшою можливою кількістю станів. Задача мінімізації має велике значення при проектуванні інтегральних схем.