Изменения

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

<tex> 1) </tex> Пусть <tex>\varepsilon \notin \alpha </tex>. тогда Тогда <tex>\forall i\geqslant 0: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex> для , следовательно <tex>\forall L \Rightarrow \alpha^{*} \beta \subset X </tex>. Пусть Докажем это индукцией по <tex>\exists z \in X, z\notin \alpha^{*} \beta: zi</tex> — самое короткое. : при <tex>zi =z_\alpha z', 0</tex> где из начального равенства <tex>z_\alpha beta \in subset X</tex>, и если <tex>\alpha ^{i} \Rightarrow z_beta \alpha \notin \varepsilon \Rightarrow z'subset X</tex> — короче , то <tex>z \Rightarrow z' \in \alpha^{*i+1} \beta = \Rightarrow z \in alpha \alpha^{*i} \beta \Rightarrow X = subset \alpha^{*} X \beta subset X</tex> .

<tex> 2)</tex> Пусть <tex>\Rightarrow varepsilon \in \alpha</tex>. Тогда можно представить этот язык в виде <tex>\alpha= \varepsilon + \alpha_{1}, \varepsilon \notin \alpha_{1}</tex>, а исходное равенство преобразуется в <tex>\varepsilon X + \alpha_{1} X + \beta = X</tex>. Теперь мы можем взять в качестве базы индукции не просто <tex>\beta</tex>, а любой язык <tex>L \supset \beta</tex>, или, что то же самое, любой <tex>\beta + L</tex>, и дальше показать <tex>\forall i \geqslant 0: {\alpha_{1}}^{*i} ( \beta + L ) = \alpha subset X \Rightarrow {\alphaalpha_{1}}^{*} ( \beta + L ) + \beta subset X</tex>, а потом отсутствие самого короткого <tex>z \in X, z \notin {\alphaalpha_{1}}^{*} (\beta + L)</tex>. Заметим, что <tex>\alpha^{*} \alpha = {\alpha^alpha_{+1}} \beta + \alpha^{*} L + \beta </tex>, тогда <tex>X = {\alphaalpha_{1}}^{*} (\beta + \alpha^{*} L ) = \alpha^{*}( \beta + \alphaL) </tex>. что и требовалось доказать

Пусть система уравнений имеет вид:

<mathtex>

\alpha_{11} x_1 X_1 + \alpha_{12} x_2 X_2 + \dots + \alpha_{1n} x_n X_n + \beta_1 = x_1 X_1 \\ \alpha_{21} x_1 X_1 + \alpha_{22} x_2 X_2 + \dots + \alpha_{2n} x_n X_n + \beta_2 = x_2X_2\\

\alpha_{n1} x_1 X_1 + \alpha_{n2} x_2 X_2 + \dots + \alpha_{nn} x_n X_n + \beta_n = x_n X_n \\\end{cases}</tex>  '''Метод решения''' Выразим <tex>X_1</tex> из первого уравнения и подставим во второе уравнение: <tex>X_2 = ( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) X_2 + (\alpha_{21} \alpha_{11}^{*} \alpha_{13} + \alpha_{23}) X_3 + \dots + (\alpha_{21} \alpha_{11}^{*} \alpha_{1n} + \alpha_{2n}) X_n</tex> <tex>+ \beta_2</tex>.  Пусть <tex> a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) </tex>, <tex> b =(\alpha_{21} \alpha_{11}^{*} \alpha_{13} + \alpha_{23}) X_3 + \dots + (\alpha_{21} \alpha_{11}^{*} \alpha_{1n} + \alpha_{2n}) 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>L_0</tex>, слова которого интерпретируются как последовательности чисел <tex>0, 1, 2</tex>, а языку удовлетворяют слова, сумма чисел в которых делится на 3. Тогда доопределив языки <tex>L_1, L_2</tex>, сумма чисел в словах из <tex>L_i</tex> равна <tex>3 - i</tex> по модулю <tex>3</tex>, получим систему уравнений в регулярных выражениях: <tex>\begin{cases}L_0 = 0L_0 + 1L_1 + 2L_2 + \varepsilon \\L_1 = 2L_0 + 0L_1 + 1L_2 \\L_2 = 1L_0 + 2L_1 + 0L_2

</mathtex> Поскольку нам нужно найти только <tex>L_0</tex>, чтобы избежать обратной прогонки, начнём выражать языки с <tex>L_2</tex>. <tex>L_2 = 0L_2 + (1L_0 + 2L_1), \varepsilon \notin 0 \Rightarrow L_2 = 0^*(1L_0+2L_1)</tex> <tex>L_1 = 2L_0 + 0L_1 + 1L_2 = 2L_0 + 0L_1 + 10^*(1L_0+2L_1) = </tex> <tex> = (0 + 10^*2)L_1 + (2 + 10^*1)L_0, \varepsilon \notin (0 + 10^*2) \Rightarrow L_1 = (0 + 10^*2)^*(2 + 10^*1)L_0</tex> <tex>L_0 = 0L_0 + 1L_1 + 2L_2 + \varepsilon = 0L_0 + 1L_1 + 20^*(1L_0 + 2L_1) + \varepsilon = </tex> <tex> = (0 + 20^*1)L_0 + (1 + 20^*2)L_1 + \varepsilon = </tex> <tex>(0 + 20^*1)L_0 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)L_0 + \varepsilon = </tex> <tex> = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))L_0 + \varepsilon </tex> <tex>\varepsilon \notin (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)) \Rightarrow </tex> <tex> \Rightarrow L_0 = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))^* </tex> == Примечания ==<references/> == См. также ==* [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]

'''метод решения'''[[Категория: Теория формальных языков]]выразим <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> \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} )</tex>. далее подставляя в полученные в ходе итераций уравнения найденный <tex> x_i </tex>, обратной прогонкой найдем <tex>x_1 \dots x_{n-1} </tex>.В разработке]]