Читайте также: |
|
Пусть языки U 1и U 2 распознаются автоматами
 1 = (A, Q 1, j1, q 0, D 1) и  2 = (A, Q 2, j2, q 1, D 2).
Построим конечный автомат Á, который функционирует из своего начального состояния так же, как и два параллельно работающих автомата Â 1 и Â 2.
Определим автомат Á как (A, Q 1 Q 2, j, (q 0, q 1), D), где D обозначает множество состояний, которое будет выбираться так, чтобы обеспечить распознавание множеств U 1È U 2, U 1Ç U 2, и U 1\ U 2.
Состояния Á - это пары (q i, q j), где q i Î Q 1 и q j Î Q 2. Начальным состоянием Á является состояние (q 0, q 1). Функция перехода j представляет собой пару функций (j1, j2), каждая из которых определяет значение соответствующей компоненты состояния Á. То есть, если в момент времени t автомат находится в состоянии (q¢ (t), q² (t)), то значение состояния Á в момент t+1 равно (j1(x (t), q¢ (t)), j2(x (t), q² (t))).
Тогда автомат Á из начального состояния (q 0, q 1) распознает множество U 1 È U 2, если в качестве множества распознающих состояний D выбрано множество
D 1 Q 2 È Q1 D 2.
Действительно, при переработке произвольного входного слова из начального состояния (q 0, q 1) компоненты состояния автомата Á изменяются так же, как состояния автоматов Â 1 и Â 2, когда эти автоматы перерабатывают из состояний q 0 и q 1 соответственно.
Поэтому Á заканчивает переработку в состоянии из D тогда и только тогда, когда автомат Â 1 заканчивает переработку в состоянии из D 1 или Â 2 заканчивает переработку этого же слова в состоянии из D 2.
То есть U 1 È U 2 Á заканчивает переработку этого слова в состоянии из множества D 1 Q 2 È Q 1 D 2.
Аналогично можно показать, что если в качестве множества распознающих состояний взять D 1 D 2, то автомат Á из начального состояния (q 0, q 1) распознает U 1Ç U 2.
Множество U 1\ U 2 распознается конечным автоматом Á, для которого D = D 1 (Q 2 \ D 2).
Если множество слов U распознается автоматом
 = (A, Q, j, q 0, D), то A * \ U распознается автоматом
(A, Q, j, q 0, Q \ D).
Дата добавления: 2015-11-30; просмотров: 26 | Нарушение авторских прав