188
правок
Изменения
Нет описания правки
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <tex>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>.
Пусть <tex>L = (P A^* \bigcap A^* S) \backslash A^* N A^*</tex> – локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:
* набор состояний <tex>Q = A \bigcup \{ \varepsilon \}</tex>,
* начальное состояние <tex>\varepsilon</tex>,
* терминальные состояния <tex>S</tex>,
* <tex>\delta(\varepsilon, a) = a</tex> если <tex>a \in P</tex> и <tex>\delta(a, b) = b</tex> если <tex>ab \not\in N</tex>.
Если <tex>L</tex> содержит пустую строку, то множество терминальных состояний <tex>\mathcal{A}</tex> – <tex>S \bigcup \{ \varepsilon \}</tex>.
{{Утверждение
|statement=Автомат <tex>\mathcal{A}</tex> – стандартный локальный автомат, распознающий <tex>L</tex>.
}}
{{Утверждение
|statement=Язык, распознаваемый локальным автоматом, является локальным.
}}
== См. также ==
