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

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

Наше деловое партнерство www.banwar.org

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

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

Теорема 4.1.

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

Лемма 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, коли отримує на вхід символ a. - це безліч станів в кожне з яких може перейти автомат зі стану q без читання символу на вході.

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

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

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

Скажімо, що заданий послідовністю ребер шлях p = e1e2 ... eT в діаграмі DM несе слово w = w1w2 ... 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. Розглянемо НКА , де

його діаграма представлена ​​нижче на Мал. 4.3 .

Діаграма автомата N1

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

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

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

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

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

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