Спирина, М.С. Дискретная математика

• функция перехода 8 ( 9 ,, Xj) задается автоматной таблицей Z, т.е. известна функция перехода при входных буквах; • для любого слова а е X* и любой буквы х} е X справедливо 5 (qh aXj) = 8 ( 8 ( 9 ,, а), *,). Фактически это значит, что, опираясь на значения функции перехода при входных буквах, мы определяем ее значения при входных словах, состоящих из большего количества букв. После­ дняя формула означает, что перед нажатием последней буквы Xj автомат после ввода слова а перешел во внутреннее состояние 9 = 8 ( 9 ,, а). Если же а = Л, то на пустое слово автомат не должен реагировать: это задает начальное условие 8 ( 9 ,, Л) = 8 ( 9 ,). Такая расширенная функция перехода дает возможность опре­ делить и расширенную функцию выхода, для которой справедли­ во X(q„ aXj) =Х( 8 ( 9 „ a ) , Xj). Событие Е с X* представимо в автомате Z = {X, Q, У, 8 , X) тогда и только тогда, когда Va е Е 3q, е Q, такое, что определено 8 ( 9 ,, а). На графе автомата события изображаются в виде подмножества всех путей, исходящих из вершины 9 ,. Событие называют предста­ вимым в конечном автомате, если существует конечный автомат, в котором оно представимо. Итак, когда событие, представимое автоматом, получено н е ­ посредственно из входного алфавита, т.е. без переходов в новые состояния, соответствующее слово является пустым. Пустое слово аналогично 1: для любого а справедливо Да = аЛ = а. Однако нельзя путать пустое слово с пустым событием, которое состоит в том, что ни одно из его заключительных состояний не может быть д о ­ стижимо из начального. Доказано, что любое конечное множество слов представимо в автомате. Однако существуют события, непредставимые в автома­ те. Так, конечные автоматы не распознают непериодические бес­ конечные последовательности слов, так как множество таких с о ­ бытий несчетно, а множество состояний автомата счетно. 7.2. Способы задания конечных автоматов Принципы —не исходный путь ис­ следования, а его конечный результат. Ф. Энгельс Существуют три способа задания конечных автоматов: • табличный (матрицы переходов и выходов); • графический (с помощью графов); • аналитический (с помощью формул). Аналитический способ. Как отмечалось в предыдущем подразде­ ле, аналитически автомат можно задать системой уравнений: 347