Изменения

[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>\mathrm{alt(L, M)}</tex>.]]

Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.

== См. также ==

* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]