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