Изменения

<wikitex>30. Доказать, что общий вид решения системы уравнений в регулярных выражениях имеет вид:Рассмотрим язык <tex> x_i = $\{w x_0 y_0 z_0 x_1 y_1 z_1 \mid w = w_dots x_{ii_1n-1}w_y_{i_1 i_2n-1} \dots w_z_{i_{kn-1} i_k} w_{i_k 0}\mid x_i, k \ge 0y_i, i_1 z_i \dots i_k \subset in \{0, 1, \dots, n}\}^k$, w_где $ X = x_{ijn-1} \in \alpha _x_{ijn-2} \} </tex>dots x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $.Докажите, что этот язык регулярный.

31. То же, что и 36, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$. 32. Рассмотрим язык <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 \{0, 1\}\}$, где $X= x_{n-1}x_{n-2} \dots x_0, $ и аналогично записывается представляется $Y $ и $Z$, причем $X + \times Y = Z\}</tex>$. Докажите, что этот язык не является регулярным. 33. Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что L регулярныйтогда и только тогда, когда синтаксический моноид L конечен. 34. Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.</wikitex>