ustify"> M={{1, 2, 3, 4}, {a, b}, D, 1, {4}}, де функція переходів D визначається так:
D (1, a)={1, 2}, D (3, a)={4}, D (2, a)={3}, D (3, b)= {4}, D (2, b)={3}. Діаграма автомата наведена на рис. 9.2, а.
Детермінований кінцевий автомат M, що допускає мова L:
M={{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}, де функція переходів D визначається так:
D (1, a)=2, D (5, a)=8, D (1, b)=1, D (5, b)=6,1000 D (2, a )=4, D (6, a)=2, D (2, b)=7, D (6, b)=1, D (3, a)=3, D (7, a)=8, D (3, b)=5, D (7, b)=6, D (4, a)=3, D (8, a)=4, D (4, b)=5, D (8, b) =7.
Діаграма автомата наведена на рис. 9.2, б.
Рис. 9.3:
Приклад 9.2. Діаграма ДКА, що допускає безліч чисел в десяткового запису, наведена на рис. 9.4.
Рис. 9.4:
Приклад 9.3. Аналіз ланцюжків.
При аналізі ланцюжка w=ababa автомат із прикладу 9.2, а, може зробити наступну послідовність тактів:
(1, ababa) (1, baba) (1, aba) (2, ba) (3, a) (4, e).
Стан 4 є заключним, отже, ланцюжок w допускається цим автоматом.
При аналізі ланцюжка w=ababab автомат із прикладу 9.2, б, повинен зробити наступну послідовність тактів:
(1, ababab) (2, babab) (7, abab) (8, bab) (7, ab) (8, b) (7, e).
Так як стан 7 не є заключним, ланцюжок w не допускається цим автоматом.
Кінцевий распознаватель - це модель пристрою з кінцевим числом станів, яке відрізняє правильно освічені, або «допустимі» ланцюжка, від «неприпустимих».
Прикладом задачі розпізнавання може служити перевірка непарності числа одиниць у довільній ланцюжку, що складається з нулів та одиниць. Відповідний кінцевий автомат допускатиме всі ланцюжки, що містять непарне число одиниць, і відкидати всі ланцюжки з парним їх числом. Назвемо його «контролером непарності».
На вхід кінцевого автомата подається ланцюжок символів з кінцевого безлічі, званого вхідним алфавітом автомата, і представляє собою сукупність символів, для роботи з якими він призначений. Як допускаються, так і відкидаємо автоматом ланцюжка, складаються тільки з символів вхідного алфавіту. Символи, які не належать вхідному алфавітом, не можна подавати на вхід автомата. Вхідний алфавіт контролера непарності складається з двох символів: «0» і «1».
У кожен момент часу кінцевий автомат має справу лише з одним вхідним символом, а інформацію про попередні символах вхідного ланцюжка зберігає за допомогою кінцевого безлічі станів. Згідно з цим поданням, автомат пам'ятає про прочитані раніше символах тільки те, що при їх обробці він перейшов в якийсь стан, яке і є пам'яттю автомата про минуле.
Контролер непарності буде побудований так, щоб він вмів запам'ятовувати, парне чи непарне число одиниць йому зустрілося при читанні вхідного ланцюжка. Виходячи з цього, безліч станів конструируемого автомата містить два стани: «чет» і «нечет».
Одне з цих станів повинно бути вибрано в якості початкового, передбачається, що автомат почне роботу в цьому стані. Початковим станом контролера непарності буде «чет», так як на першому кроці число прочитаних одиниць дорівнює нулю, а нуль - парне число.
При читанні чергового символу стан автомата змінюється, причому новий його стан залежить тільки від вхідн...
