Местный язык (формальный язык)

В математике локальный язык — это формальный язык , для которого принадлежность слова к языку может быть определена путем просмотра первого и последнего символа и каждой двухсимвольной подстроки слова. Эквивалентно, это язык, распознаваемый локальным автоматом , особым видом детерминированного конечного автомата .

Формально язык L в алфавите A считается локальным , если существуют подмножества R и S алфавита A и подмножество F алфавита A × A такие, что слово w находится в L тогда и только тогда, когда первая буква слова w находится в алфавите A. R , последняя буква w находится в S и ни один фактор длины 2 в w не находится в F. , Это соответствует регулярному выражению

$(RA^{*}\cap A^{*}S)\setminus A^{*}FA^{*}\ .$

В более общем смысле, k - тестируемый язык L — это язык, для которого принадлежность слова w к L зависит только от префикса и суффикса длины k и набора факторов w длины k ; язык является локально тестируемым, если он k -тестируем для некоторого k . Локальный язык 2-тестируем.

Примеры

• Над алфавитом { a , b , [ , ] }

$aa^{*},\ [ab]\ .$

Характеристики

• Семейство локальных языков над A замкнуто относительно пересечения и звезды Клини , но не является дополнением, объединением или конкатенацией.
• Каждый регулярный язык, не содержащий пустой строки, является образом локального языка при строго алфавитном морфизме .

Ссылки

• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл/CRC. ISBN  1-58488-255-7 . Збл   1086.68074 .
• Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Научная монография. Том. 65. С приложением Уильяма Хеннемана. МТИ Пресс. ISBN  0-262-13076-9 . Збл   0232.94024 .
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-84425-3 . Збл   1188.68177 .
• Саломаа, Арто (1981). Жемчужины теории формального языка . Издательство Питман. ISBN  0-273-08522-0 . Збл   0487.68064 .