Изменения

Перейти к: навигация, поиск

Решение уравнений в регулярных выражениях

759 байт добавлено, 14:26, 9 января 2015
Решение уравнений в регулярных выражениях: Изменение доказательства
если <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\geqslant 0: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex> для , следовательно <tex> \alpha^{*} \beta \subset X </tex>. Докажем это индукцией по <tex>i</tex>: при <tex>i = 0</tex> из начального равенства <tex>\beta \subset X</tex>, и если <tex>\forall alpha^{i} \beta \subset X</tex>, тогда то <tex> \alpha^{*i+1} \beta = \alpha \alpha^{i} \beta \subset \alpha X \subset X </tex>.
Пусть существует <tex> z \in X,\, z\notin \alpha^{*} \beta</tex> такой, что <tex> z </tex> — самое короткое; тогда <tex>z \notin \beta \subset \alpha^{*} \beta \Rightarrow z \in \alpha X, z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha , z' \in X </tex>.
Тогда <tex> z_\alpha \notin ne \varepsilon \Rightarrow z'</tex> короче <tex>z </tex>, противоречие, тогда не существует самого короткого <tex>z</tex>, значит не существует никакого.
Следовательно <tex> z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex>.
 <tex> 2)</tex> Пусть <tex> \varepsilon \in \alpha</tex>. Выберем Тогда можно представить этот язык в качестве виде <tex>L\alpha = \varepsilon + \alpha_{1}, \varepsilon \notin \alpha_{1}</tex> любой язык и предположим, что а исходное равенство преобразуется в <tex> \alpha^varepsilon X + \alpha_{*1}( X + \beta + L) = X</tex> — решение.  Тогда Теперь мы можем взять в качестве базы индукции не просто <tex> \alpha^{*}( \beta + L) </tex> подходит в , а любой язык <tex>X = L \alpha X + supset \beta</tex>.  Следовательно, для него выполняется: или, что то же самое, любой <tex> \alpha^{*} ( \beta + L ) = </tex>, и дальше показать <tex>\forall i \alpha geqslant 0: {\alphaalpha_{1}}^{*i} ( \beta + L ) + \beta subset X \Rightarrow {\alphaalpha_{1}}^{*} (\beta + L) \alpha^{*} \alpha subset X</tex> , а потом отсутствие самого короткого <tex>= z \in X, z \notin {\alpha^alpha_{+1}} \beta + \alpha^{*} L + (\beta + L)</tex> . Заметим, что <tex>= \alpha^{*} ={\beta + \alphaalpha_{1}}^{*} L </tex> , тогда <tex>X = {\alpha_{1}}^{*}(\beta + L) = \alpha^{*}( \beta + L) </tex>.
}}
120
правок

Навигация