Еквівалентність детермінованих і недетермінірованних кінцевих автоматів - це

Еквівалентність детермінованих і недетермінірованних кінцевих автоматів

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

Існують різні варіанти завдання кінцевого автомата. Наприклад, кінцевий автомат може бути заданий за допомогою п'яти параметрів: де:

• Q - кінцеве безліч станів автомата;
• q0 - початковий стан автомата ();
• F - безліч заключних (або допускають) станів, таких що;
• Σ - допустимий вхідний алфавіт (кінцеве безліч допустимих вхідних символів), з якого формуються рядки, зчитувальні автоматом;
• δ - заданий відображення безлічі в безліч підмножин Q: (іноді δ називають функцією переходів автомата).

Автомат починає роботу в стані q0. зчитуючи по одному символу вхідного рядка. Лічені символ переводить автомат в новий стан з Q відповідно до функції переходів. Якщо по завершенні зчитування вхідного слова (ланцюжки символів) автомат виявляється в одному з допускають станів, то слово «приймається» автоматом. У цьому випадку говорять, що воно належить мові даного автомата. В іншому випадку слово «відкидається».

Інші способи опису

1. Діаграма станів (або іноді граф переходів) - графічне представлення безлічі станів і функції переходів. Являє собою навантажений односпрямований граф. вершини якого - стану КА, дуги - переходи з одного стану в інший, а навантаження - символи, при яких здійснюється даний перехід. Якщо перехід зі стану q1 в q2 може бути здійснений при появі одного з декількох символів, то над дугою повинні бути надписані все вони.
2. Таблиця переходів - табличне представлення функції δ. Зазвичай в такій таблиці кожному рядку відповідає один стан, а одну - один допустимий вхідний символ. В осередку на перетині рядка і стовпця записується дію, яку повинен виконати автомат, якщо в ситуації, коли він перебував в даному стані на вході він отримав даний символ.

детермінованість

Кінцеві автомати підрозділяються на детерміновані і недетерміновані.

Детермінований кінцевий автомат

• Детермінованим кінцевим автоматом (ДКА) називається такий автомат, в якому для кожної послідовності вхідних символів існує лише один стан, в яке автомат може перейти з поточного.

• Недетермінований кінцевий автомат (НКА) є узагальненням детермінованого. Недетермінірованность автоматів досягається двома способами:

Існують переходи, помічені порожній ланцюжком ε

З одного стану виходить кілька переходів, позначених одним і тим же символом