Местный язык (официальный язык) - Local language (formal language)
В математике местный язык это формальный язык для которого принадлежность слова к языку можно определить, посмотрев на "окно"[требуется разъяснение ] длины два.[1] Точно так же это язык, признанный локальный автомат, особый вид детерминированный конечный автомат.[2]
Формально язык L над алфавитом А определяется как местный если есть подмножества р и S из А и подмножество F из А×А такое, что слово ш в L тогда и только тогда, когда первая буква ш в р, последняя буква ш в S и нет множителя длины 2 дюйма ш в F.[3] Это соответствует регулярное выражение[1][4]
В более общем плане k-проверяемый язык L тот, для которого членство в слове ш в L зависит только от префикса, суффикса и набора факторов ш длины k; язык локально проверяемый если это k-проверенный для некоторых k.[5] Местный язык можно тестировать дважды.[1]
Примеры
- Над алфавитом {а,б,[,]}[4]
![{ displaystyle aa ^ {*}, [ab] .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e32cc6bcb12d719a8bd7b714c95e953b40fdb17)
Характеристики
- Семья местных языков более А замкнуто относительно пересечения и Клини звезда, но не дополнение, объединение или конкатенация.[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.