Решение уравнений в регулярных выражениях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Утверждение |statement= Пусть уравнение имеет вид<tex>X = \alpha X + \beta</tex>, тогда: если <tex>\varepsilon \notin \al…»)
 
Строка 5: Строка 5:
 
|proof=
 
|proof=
 
<tex> 1) \varepsilon \notin \alpha </tex>. тогда <tex>\forall i:  \alpha^{i} \beta \subset X </tex> для <tex>\forall \alpha \Rightarrow \alpha^{*} \beta \subset X </tex>. Пусть <tex>\exists z \in X, z\notin \alpha^{*} \beta: z</tex> — самое короткое. <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha \Rightarrow z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z \Rightarrow z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex>  
 
<tex> 1) \varepsilon \notin \alpha </tex>. тогда <tex>\forall i:  \alpha^{i} \beta \subset X </tex> для <tex>\forall \alpha \Rightarrow \alpha^{*} \beta \subset X </tex>. Пусть <tex>\exists z \in X, z\notin \alpha^{*} \beta: z</tex> — самое короткое. <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha \Rightarrow z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z \Rightarrow z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex>  
 +
 +
 +
 +
<tex> 2) \varepsilon \in \alpha</tex>. <tex> \alpha^{*} \beta \subset X  </tex>. <tex>\alpha \beta \subset X</tex>. выберем в качестве <tex>\alpha</tex> любой язык. <tex>\Rightarrow  \alpha^{*} ( \beta + \alpha ) =  \alpha  \alpha^{*} ( \beta + \alpha ) +  \beta =  \alpha^{*} ( \beta + \alpha ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha = \alpha^{*} \beta + \alpha^{*} \alpha + \beta  </tex>. выберем <tex> \alpha = X </tex>.
  
 
}}
 
}}

Версия 13:37, 7 октября 2010

Утверждение:
Пусть уравнение имеет вид[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 \alpha \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 \subset X [/math]. [math]\alpha \beta \subset X[/math]. выберем в качестве [math]\alpha[/math] любой язык. [math]\Rightarrow \alpha^{*} ( \beta + \alpha ) = \alpha \alpha^{*} ( \beta + \alpha ) + \beta = \alpha^{*} ( \beta + \alpha ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha = \alpha^{*} \beta + \alpha^{*} \alpha + \beta [/math]. выберем [math] \alpha = X [/math].
[math]\triangleleft[/math]