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

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

Утверждение:

Пусть уравнение имеет вид [math]X = \alpha X + \beta[/math], тогда: если [math]\varepsilon \notin \alpha \Rightarrow \alpha^{*} \beta[/math] — единственное решение. если [math]\varepsilon \in \alpha \Rightarrow \alpha^{*}( \beta + \alpha)[/math] — решение для [math]\forall \alpha[/math]

[math]\triangleright[/math]

[math] 1) \varepsilon \notin \alpha [/math]. тогда [math]\forall i: \alpha^{i} \beta \subset X [/math] для [math]\forall L \Rightarrow \alpha^{*} \beta \subset X [/math]. Пусть [math]\exists z \in X, z\notin \alpha^{*} \beta: z[/math] — самое короткое. [math]z=z_\alpha z', [/math] где [math]z_\alpha \in \alpha \Rightarrow z_\alpha \notin \varepsilon \Rightarrow z'[/math] — короче [math]z \Rightarrow z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta [/math] [math] 2) \varepsilon \in \alpha[/math]. предположим, что [math] \alpha^{*}( \beta + \alpha) [/math] — решение, тогда [math] \alpha^{*}( \beta + \alpha) [/math] подходит в [math]X = \alpha X + \beta[/math]. Выберем в качестве [math]L[/math] любой язык. [math]\Rightarrow \alpha^{*} ( \beta + L ) = \alpha \alpha^{*} ( \beta + L ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha = \alpha^{+} \beta + \alpha^{*} L + \beta = \alpha^{*} \beta + \alpha^{*} L = \alpha^{*}( \beta + \alpha) [/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} ) \Rightarrow 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].