188
правок
Изменения
→Локальный язык
{{Утверждение
|statement=Автомат <tex>\mathcal{A}</tex> – стандартный локальный автомат, распознающий <tex>L</tex>.
|proof=
Автомат является локальным поскольку для каждого состояния <tex>s</tex> и любого символа <tex>a</tex> <tex>\delta(s, a)</tex> либо неопределена либо равна <tex>a</tex>. По построению автомат является стандартным. <br>
Покажем, что <tex>L(\mathcal{A}) = L</tex>. Пусть <tex>x = a_1 \ldots a_n \in L(\mathcal{A})</tex>. Тогда в автомате существует путь: <br>
:<tex>\varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n-1} \xrightarrow{a_n} a_n</tex>.
Здесь <tex>a_n</tex> {{---}} терминальное состояние, <tex>a_n \in S</tex>. Переход из <tex>\varepsilon</tex> в <tex>a_1</tex> определен, поэтому <tex>a_1 \in P</tex>. Для каждого <tex>j</tex> такого что <tex>1 \leqslant j \leqslant n - 1</tex> факт, что переход <tex>a_j \rightarrow a_{j+1}</tex> существует, означает что <tex>a_j a_{j+1} \not \in N</tex>.<br>Следовательно, <tex>x \in L</tex>.
}}
