211
правок
Изменения
м
→Определения
{{Определение
|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>.
}}
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> '''эквивалентны''', если они неразличимы не различимы никакой строкой <tex>s</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>
