В інформатиці та математичній теорії формальних мов, локальна мова (2-тестова мова) — це формальна мова, кожне слово якої задається першою й останньою буквами та множиною недопустимих підслів. Будь-якій локальній мові можна поставити у відповідність локальний автомат, підвид детермінованого скінченного автомата.
Визначення
Мова над алфавітом називається локальною, якщо існують такі мови , та , що
, ,
Приклади
Розглянемо алфавіт та мови над . , , . Мова є локальною.
Властивості
Будь-яка локальна мова є автоматною. Мова над алфавітом , що не містить порожнього слова, є регулярною тоді і лише тоді, коли існують такі алфавіт , локальна мова і побуквенний гомоморфізм , що . Для перевірки чи належить слово локальній мові , достатньо локально переглядати підслова слова довжиною 2. Локальні мови є окремим випадком -тестових мов, з .
Література