|
|
| Строка 5: |
Строка 5: |
| | |statement= | | |statement= |
| | Пусть уравнение имеет вид <tex> X = \alpha X + \beta \Rightarrow \, 1)</tex> | | Пусть уравнение имеет вид <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> | + | если <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= | | |proof= |
| − | <tex> 1) </tex> Пусть <tex>\varepsilon \notin \alpha </tex>. тогда <tex>\forall i: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex> для <tex>\forall X</tex>, тогда <tex> \alpha^{*} \beta \subset X </tex>. Пусть существует<tex> z \in X,\, z\notin \alpha^{*} \beta</tex> такой, что <tex> z </tex> — самое короткое. <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha </tex>, тогда <tex> z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z </tex>. Следовательно <tex> z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex>. | + | <tex> 1) </tex> Пусть <tex>\varepsilon \notin \alpha </tex>. Тогда <tex>\forall i: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex> для <tex>\forall X</tex>, тогда <tex> \alpha^{*} \beta \subset X </tex>. |
| | | | |
| | + | Пусть существует <tex> z \in X,\, z\notin \alpha^{*} \beta</tex> такой, что <tex> z </tex> — самое короткое; <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha </tex>. |
| | | | |
| | + | Тогда <tex> z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z </tex>. |
| | | | |
| − | <tex> 2)</tex> Пусть <tex> \varepsilon \in \alpha</tex>. Выберем в качестве <tex>L</tex> любой язык и предположим, что <tex> \alpha^{*}( \beta + L) </tex> — решение, тогда <tex> \alpha^{*}( \beta + L) </tex> подходит в <tex>X = \alpha X + \beta</tex>. Тогда для него выполняется: <tex> \alpha^{*} ( \beta + L ) = \alpha \alpha^{*} ( \beta + L ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha </tex> <tex>= \alpha^{+} \beta + \alpha^{*} L + \beta = \alpha^{*} \beta + \alpha^{*} L = \alpha^{*}( \beta + L) </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</tex> любой язык и предположим, что <tex> \alpha^{*}( \beta + L) </tex> — решение. Тогда <tex> \alpha^{*}( \beta + L) </tex> подходит в <tex>X = \alpha X + \beta</tex>. Тогда для него выполняется: <tex> \alpha^{*} ( \beta + L ) = \alpha \alpha^{*} ( \beta + L ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha </tex> <tex>= \alpha^{+} \beta + \alpha^{*} L + \beta = \alpha^{*} \beta + \alpha^{*} L = \alpha^{*}( \beta + L) </tex>. Что и требовалось доказать. |
| | | | |
| | }} | | }} |
| Строка 29: |
Строка 35: |
| | | | |
| | | | |
| − | '''метод решения''' | + | '''Метод решения''' |
| − | выразим <tex>x_1</tex> из первого уравнения и подставим во второе уравнение: <tex> X_2 = ( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) X_2 + \alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2</tex>. Пусть <tex> a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) </tex>, <tex> b =\alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2 </tex>, тогда уравнение примет вид <tex>X_2=a X_2 + b</tex>. его решением будет <tex>a^{*} b</tex>. подставим в следующее уравнение выраженный <tex>X_2</tex>, далее выполняя схожие итерации получим уравнение <tex>X_n = a' X_n + b'</tex>, где <tex> a'=f( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ),\, b'=g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ) </tex>, тогда <tex>X_n= f^{*}( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )</tex>. далее подставляя в полученные в ходе итераций уравнения найденный <tex> X_i </tex>, обратной прогонкой найдем <tex>X_1 \dots X_{n-1} </tex>.
| + | |
| | + | Выразим <tex>X_1</tex> из первого уравнения и подставим во второе уравнение: <tex> X_2 = ( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) X_2 + \alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2</tex>. |
| | + | |
| | + | Пусть <tex> a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) </tex>, <tex> b =\alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2 </tex>, тогда уравнение примет вид <tex>X_2=a X_2 + b</tex>. Его решением будет <tex>a^{*} b</tex>. Подставим в следующее уравнение выраженный <tex>X_2</tex>. |
| | + | |
| | + | Далее выполняя схожие итерации получим уравнение <tex>X_n = a' X_n + b'</tex>, где <tex> a'=f( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ),\, b'=g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ) </tex>, тогда <tex>X_n= f^{*}( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )</tex>. |
| | + | |
| | + | Далее подставляя в полученные в ходе итераций уравнения найденный <tex> X_i </tex>, обратной прогонкой найдем <tex>X_1 \dots X_{n-1} </tex>. |
Решение уравнений в регулярных выражениях
Пусть [math]X[/math] — некий язык, для которого выполняется равенство [math]X = \alpha X + \beta [/math], где [math]\alpha,\,\beta[/math] — некие регулярные выражения над неким алфавитом [math]A[/math].
| Утверждение: |
Пусть уравнение имеет вид [math] X = \alpha X + \beta \Rightarrow \, 1)[/math]
если [math]\varepsilon \notin \alpha [/math], тогда [math] \alpha^{*} \beta[/math] — единственное решение [math]2)[/math] если [math]\varepsilon \in \alpha [/math], тогда [math] \alpha^{*}( \beta + L)[/math] — решение для [math]\forall L[/math] |
| [math]\triangleright[/math] |
|
[math] 1) [/math] Пусть [math]\varepsilon \notin \alpha [/math]. Тогда [math]\forall i: [/math] выражение [math]\alpha^{i} \beta \subset X [/math] для [math]\forall X[/math], тогда [math] \alpha^{*} \beta \subset X [/math].
Пусть существует [math] z \in X,\, z\notin \alpha^{*} \beta[/math] такой, что [math] z [/math] — самое короткое; [math]z=z_\alpha z', [/math] где [math]z_\alpha \in \alpha [/math].
Тогда [math] z_\alpha \notin \varepsilon \Rightarrow z'[/math] — короче [math]z [/math].
Следовательно [math] z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta [/math].
[math] 2)[/math] Пусть [math] \varepsilon \in \alpha[/math]. Выберем в качестве [math]L[/math] любой язык и предположим, что [math] \alpha^{*}( \beta + L) [/math] — решение. Тогда [math] \alpha^{*}( \beta + L) [/math] подходит в [math]X = \alpha X + \beta[/math]. Тогда для него выполняется: [math] \alpha^{*} ( \beta + L ) = \alpha \alpha^{*} ( \beta + L ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha [/math] [math]= \alpha^{+} \beta + \alpha^{*} L + \beta = \alpha^{*} \beta + \alpha^{*} L = \alpha^{*}( \beta + L) [/math]. Что и требовалось доказать. |
| [math]\triangleleft[/math] |
Решение системы уравнений в регулярных выражениях
Пусть система уравнений имеет вид
[math]
\begin{cases}
\alpha_{11} X_1 + \alpha_{12} X_2 + \dots + \alpha_{1n} X_n + \beta_1 = X_1 \\
\alpha_{21} X_1 + \alpha_{22} X_2 + \dots + \alpha_{2n} X_n + \beta_2 = X_2\\
\dots\\
\alpha_{n1} X_1 + \alpha_{n2} X_2 + \dots + \alpha_{nn} X_n + \beta_n = X_n \\
\end{cases}
[/math]
Метод решения
Выразим [math]X_1[/math] из первого уравнения и подставим во второе уравнение: [math] X_2 = ( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) X_2 + \alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2[/math].
Пусть [math] a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) [/math], [math] b =\alpha_{21} \alpha_{11}^{*} \alpha_{13} X_3 + \dots + \alpha_{21} \alpha_{11}^{*} \alpha_{1n} X_n + \beta_2 [/math], тогда уравнение примет вид [math]X_2=a X_2 + b[/math]. Его решением будет [math]a^{*} b[/math]. Подставим в следующее уравнение выраженный [math]X_2[/math].
Далее выполняя схожие итерации получим уравнение [math]X_n = a' X_n + b'[/math], где [math] a'=f( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ),\, b'=g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ) [/math], тогда [math]X_n= f^{*}( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )[/math].
Далее подставляя в полученные в ходе итераций уравнения найденный [math] X_i [/math], обратной прогонкой найдем [math]X_1 \dots X_{n-1} [/math].
