577
правок
Изменения
→Язык alt(L, M)
{{Определение
|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>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>cycle(L)</tex> ===
{{Определение
