188
правок
Изменения
→Локальный язык
Рассмотрим язык, распознаваемый стандартным локальным автоматом.
{{Определение
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \backslash setminus \varepsilon</tex> может быть описан следующим образом: <br><tex>\exists P, S \subseteq A, N \subseteq A^2: L \backslash setminus \varepsilon = (P A^* \cap A^* S) \backslash setminus A^* N A^*</tex>.
}}
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <tex>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>.
Пусть <tex>L = (P A^* \cap A^* S) \backslash setminus A^* N A^*</tex> {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:
* набор состояний <tex>Q = A \cup \{ \varepsilon \}</tex>,
* начальное состояние <tex>\varepsilon</tex>,
