Ноу Інти, лекція, кінцеві автомати перетворювачі і розпізнавачі

твір автоматів

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

Нехай і - два кінцевих автомата із загальним вхідним алфавітом розпізнають мови L1 і L2. відповідно. Визначимо по ним автомат M =, званий твором M1 і M2 (M = M1 x M2). наступним чином. , Тобто стану нового автомата - це пари, перший елемент яких - стан першого автомата, а другий - стан другого автомата. Для кожної такої пари (q, p) і вхідного символу визначимо функцію переходів. . Початковим станом M є пара q0 = (q0 1. q0 2). що складається з початкових станів автоматів-множників. Що стосується безлічі заключних станів. то воно визначається в залежності від операції над мовами L1 і L2. яку повинен реалізувати M.

• При чи автомат розпізнає мову.
• При і автомат розпізнає мову.
• При і автомат M = розпізнає мову L = L1 \ L2.

Доказ цієї теореми безпосередньо виводиться з наступного твердження.

Лемма 4.2. Для будь-яких двох станів (q, p) і (q ', p') автомата M і будь-якого вхідного слова w слово w переводить (q, p) в (q ', p') в автоматі M тоді і тільки тоді, коли воно переводить q в q 'в автоматі M1 і p в p' в автоматі M2.

Лемма встановлюється індукцією по довжині слова w.

Следствіе4.1.1. Клас звичайно автоматних мов замкнутий щодо теоретико множинних операцій об'єднання, перетину і різниці.

Недетермінірованние кінцеві автомати та їх детермінізації

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

Визначення 4.8. Недетермінований кінцевий автомат (НКА) - распознаватель - це система виду

що включає наступні компоненти:

• - кінцеве безліч - вхідний алфавіт;
• Q = 0. qn-1> (n> = 1) - кінцеве безліч - алфавіт внутрішніх станів;
• - початковий стан автомата;
• - безліч приймають (допускають, заключних) станів;
• - функція переходів.

Для значення - це безліч станів в кожне з яких може перейти автомат зі стану q. коли отримує на вхід символ a. - це безліч станів в кожне з яких може перейти автомат зі стану q без читання символу на вході.

Як і для детермінованих автоматів, функцію переходів можна уявити за допомогою набору команд-програми: для кожної пари і та кожного стану в програму поміщається команда q a -> q '. і для кожного стану в програму поміщається команда q -> q '. Відмінність від детермінованого випадку полягає в тому, що для однієї пари і в програмі може бути кілька команд виду q a -> q 'чи не бути жодної такої команди. Крім того, можуть з'явитися-команда (порожні переходи) виду q -> q '. означають можливість безпосереднього переходу з q в q 'без читання символу на вході.

При табличному завданні функції в таблиці з'являється (m + 1) -ий стовпець, відповідний порожньому символу і на перетині рядка q і стовпці стоїть безліч станів.

Для недетермінірованного автомата в діаграмі DM = (Q, E) з виділеної початковою вершиною q0 і безліччю заключних вершин F ребра взаємно-однозначно відповідають командам: команді виду q a -> q 'відповідає ребро (q, q'), з міткою a. а команді виду q -> q 'відповідає ребро (q, q'), з міткою.

Скажімо, що заданий послідовністю ребер шлях p = e1 e2. eT в діаграмі DM несе слово w = w1 w2. wt (t <= T). если после удаления из него "пустых" ребер (т.е. ребер с метками ) остается последовательность из t ребер , метки которых образуют слово w. т.е. wi - это метка ребра . Очевидно, это эквивалентно тому, что последовательность меток на ребрах пути p имеет вид , где kj>= 0 (j = 1,2. T + 1) і.

Слово w переводить q в q 'в діаграмі DM. якщо в ній є шлях з q в q 'який несе w.

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

Визначення 4.9. Назвемо конфігурацією НКА довільну пару виду (q, w). в якій і. Визначимо відношення переходу з однієї конфігурації в іншу за один крок:

Як і для ДКА, через позначимо рефлексивне і транзитивне замикання відношення.

Зовні визначення розпізнавання слів НКА збігається з визначенням для ДКА.

Визначення 4.10. НКА M розпізнає (допускає, приймає) слово w. якщо для деякого \

Мова LM. розпізнається НКА M. складається з усіх слів. розпізнаються автоматично:

Відмінність полягає в тому, що у НКА може бути кілька різних способів роботи (шляхів обчислення) на одному і тому ж вхідному слові w. Вважаємо, що НКА розпізнає (допускає, приймає) це слово. якщо хоча б один з цих способів призводить до заключного стан з F.

З визначення діаграми DM безпосередньо випливає, що НКА M розпізнає слово w. тоді і тільки тоді, коли існує таке заключне стан, що в діаграмі DM слово w переводить q0 в q. Іншими словами, в DM є шлях з q0 в q. на ребрах якого написано слово w (з точністю до міток).

Приклад 4.1. Розглянемо НКА, де

Розглянемо роботу цього автомата на слові ababa:

Так як 3 - заключне стан, то. Зауважимо, що у автомата N1 є й інші способи роботи на цьому слові. не ведуть до заключного стану. Наприклад, він може після читання кожного символу залишатися в стані 0. Але щоб слово допускалося, досить існувати хоча б одному "доброго" способу.

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

Теорема 4.2. (Детермінізації НКА)

Для кожного НКА M можна ефективно побудувати такий ДКА A. що LA = LM.

Доказ Нехай - НКА. Процедура побудови по ньому еквівалентного ДКА складається з двох етапів: на першому по M будується еквівалентний йому НКА M1. в програмі якого відсутні переходи по а на другому етапі по M1 будується еквівалентний ДКА A.