Y2010. 5 семестр. Домашние задания. — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
<tex> x_i = \{w \mid w = w_{ii_1}w_{i_1 i_2} \dots w_{i_{k-1} i_k} w_{i_k 0}, k \ge 0, i_1 \dots i_k \subset \{1, \dots, n\}^k, w_{ij} \in \alpha _{ij} \} </tex>
 
<tex> x_i = \{w \mid w = w_{ii_1}w_{i_1 i_2} \dots w_{i_{k-1} i_k} w_{i_k 0}, k \ge 0, i_1 \dots i_k \subset \{1, \dots, n\}^k, w_{ij} \in \alpha _{ij} \} </tex>
  
36. Рассмотрим язык <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 + Y = Z\}</tex>. Докажите, что этот язык регулярный.
+
36. Рассмотрим язык  
 +
<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\}\}</tex>, где <tex> X = x_{n-1}x_{n-2}\dots x_0</tex> и аналогично представляется <tex>Y</tex> и <tex>Z</tex>, причем <tex> X + Y = Z </tex>.
 +
Докажите, что этот язык регулярный.
 +
 
 +
37. То же, что и 36, только <tex>\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}</tex>.

Версия 16:09, 24 сентября 2012

30. Доказать, что общий вид решения системы уравнений в регулярных выражениях имеет вид: [math] x_i = \{w \mid w = w_{ii_1}w_{i_1 i_2} \dots w_{i_{k-1} i_k} w_{i_k 0}, k \ge 0, i_1 \dots i_k \subset \{1, \dots, n\}^k, w_{ij} \in \alpha _{ij} \} [/math]

36. Рассмотрим язык [math]\{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\}\}[/math], где [math] X = x_{n-1}x_{n-2}\dots x_0[/math] и аналогично представляется [math]Y[/math] и [math]Z[/math], причем [math] X + Y = Z [/math]. Докажите, что этот язык регулярный.

37. То же, что и 36, только [math]\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}[/math].