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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
30. Доказать, что общий вид решения системы уравнений в регулярных выражениях имеет вид:
+
<wikitex>
−
<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>
+
30. Рассмотрим язык
 +
$\{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 $.
 +
Докажите, что этот язык регулярный.
 +
 
 +
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. Рассмотрим язык
 +
$\{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$.
 +
Докажите, что этот язык не является регулярным.
  
−
36. Рассмотрим язык
+
33. Рассмотрим отношение на словах $L$:  $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что L регулярный тогда и только тогда, когда синтаксический моноид L конечен.
−
<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>.
+
34. Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
 +
</wikitex>

Версия 15:39, 20 сентября 2013

<wikitex> 30. Рассмотрим язык $\{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 $. Докажите, что этот язык регулярный.

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. Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.

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>

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Y2010._5_семестр._Домашние_задания.&oldid=32832»