Изменения

Автомат является локальным поскольку для каждого состояния <tex>s</tex> и любого символа <tex>a</tex> <tex>\delta(s, a)</tex> либо неопределена либо равна <tex>a</tex>. По построению автомат является стандартным. <br>Покажем, что <tex>L(\mathcal{A}) = L</tex>. <br>Пусть <tex>x = a_1 \ldots a_n \in L(\mathcal{A})</tex>. Тогда в автомате существует путь: <br>

Здесь <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>.Следовательно, <tex>x \in L</tex>.  Пусть <tex>x = a_1 \ldots a_n \in L</tex>. Тогда <tex>a_1 \in P</tex>, <tex>a_n \in S</tex> и для каждого <tex>j</tex> <tex>a_j a_{j+1} \not \in N</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>x \in L(\mathcal{A})</tex>.