Изменения

<wikitex>30. Доказать, что общий вид решения системы уравнений в регулярных выражениях имеет вид:Рассмотрим язык <tex> $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i = , y_i, z_i \in \{w 0, 1\mid w }\}$, где $ X = w_x_{ii_1n-1}w_x_{i_1 i_2n-2} \dots w_x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $.Докажите, что этот язык регулярный. 31. То же, что и 36, только $\{i_x_{kn-1} i_ky_{n-1} w_z_{i_k 0n-1}, k \ge 0, i_1 dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots i_k \subset }$. 32. Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \dots{0, n1\}\}^k$, w_где $X = x_{n-1}x_{ijn-2} \dots x_0$ и аналогично представляется $Y$ и $Z$, причем $X \times Y = Z$.Докажите, что этот язык не является регулярным. 33. Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \alpha _{ij} Leftrightarrow uyv \} in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что L регулярный тогда и только тогда, когда синтаксический моноид L конечен. 34. Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.</texwikitex>