В математике местный язык - это формальный язык, для которого принадлежность слова к языку может быть определена по первому и последнему символу и каждой двухсимвольной подстроке слова. [1] Эквивалентно, это язык, распознаваемый локальным автоматом , определенным видом детерминированного конечного автомата . [2]
Формально язык L над алфавитом A определяется как локальный, если существуют подмножества R и S в A и подмножество F в A × A, такое что слово w находится в L тогда и только тогда, когда первая буква слова w находится в R , последняя буква ж в S и не фактор длины 2 в ш в F . [3] Это соответствует регулярному выражению [1] [4]
В более общем случае к - проверяемым язык L является один , для которых членство слова ш в L зависит только от префикса, суффикса [ далее объяснение необходимости ] и множество факторов ш длины к ; язык является локально тестируемым, если он является k- тестируемым для некоторого k . [5] Местный язык можно тестировать дважды. [1]
Примеры
- Над алфавитом { a , b , [ , ] } [4]
Характеристики
- Семейство локальных языков над A замкнуто относительно пересечения и звезды Клини , но не дополнения, объединения или конкатенации. [4]
- Каждый регулярный язык, не содержащий пустой строки, является образом местного языка в строго алфавитном морфизме . [1] [6] [7]
Рекомендации
- Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл / CRC. ISBN 1-58488-255-7. Zbl 1086.68074 .
- Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Монография исследований. 65 . С приложением Уильяма Хеннемана. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024 .
- Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Zbl 1188.68177 .
- Саломаа, Арто (1981). Драгоценности теории формального языка . Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064 .