Изменения
→Определения
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> , если
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle </tex>, где <tex>z \notin T </tex>
Если <tex>u</tex> и <tex>v</tex>, <tex>v</tex> и <tex>z</tex> эквивалентны, то <tex>u</tex> и <tex>z</tex> эквивалентны.
|proof =
Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex>, такой, что
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>.
Рассмотрим <tex>x</tex>, такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. <br>
Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. <br>
Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. <br>
