120
правок
Изменения
м
→Решение уравнений в регулярных выражениях
<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>\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 , z' \notin \alpha^{*} \beta </tex>.
Тогда <tex> z_\alpha \ne \varepsilon \Rightarrow z'</tex> короче <tex>z</tex>, противоречие, тогда не существует самого короткого <tex>z</tex>, значит не существует никакого.
