577
правок
Изменения
Нет описания правки
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык <tex>cycle(L)</tex> ===
{{Определение
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.<br>
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.
<br><br><br><br><br><br><br><br><br><br><br>
=== Язык <tex>alt(L, M)</tex> ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>alt(L, M) = \{ 1101, 0101, 10010011 \}</tex>.
{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>alt(L, M)</tex>, что доказывает, что <tex>alt(L, M)</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>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>.
