Изменения
Нет описания правки
==Решение уравнений в регулярных выражениях==
Пусть <tex>A</tex> — некий алфавит, <tex>\alpha,\,\beta</tex> — некие регулярные выражения над этим алфавитом. X - некий язык к которому мы применяем эти регулярные выражения.
{{Утверждение
|statement=
Пусть уравнение имеет вид <tex>X = \alpha X + \beta \Rightarrow \, 1)</tex>
если <tex>\varepsilon \notin \alpha </tex>, тогда <tex> \alpha^{*} \beta</tex> — единственное решение. <tex>2)</tex> если <tex>\varepsilon \in \alpha </tex>, тогда <tex> \alpha^{*}( \beta + L)</tex> — решение для <tex>\forall L</tex>
|proof=
<tex> 1) </tex> Пусть <tex>\varepsilon \notin \alpha </tex>. тогда <tex>\forall i: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex> для <tex>\forall L \Rightarrow X</tex>, тогда <tex> \alpha^{*} \beta \subset X </tex>. Пусть существует<tex>\exists z \in X,\, z\notin \alpha^{*} \beta: </tex> такой, что <tex> z</tex> — самое короткое. <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha \Rightarrow </tex>, тогда <tex> z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z \Rightarrow </tex>. Следовательно <tex> z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex> .
