Локальна мова

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

Визначення

Мова $L\subseteq {\Sigma }^{\ast }$ над алфавітом $\Sigma$ називається локальною, якщо існують такі мови $L_1\subseteq {\Sigma }^{\ast }$,$L_2\subseteq {\Sigma }^{\ast }$ та $L_3\subseteq {\Sigma }^{\ast }$, що

• $\mathrm{\forall }w\in L_{1,2}:|w|=1$,
• $\mathrm{\forall }w\in L_3:|w|=2$,
• $L=((L_1\cdot {\Sigma }^{\ast })\cap ({\Sigma }^{\ast }\cdot L_2))\setminus ({\Sigma }^{\ast }\cdot L_3\cdot {\Sigma }^{\ast })$

Приклади

• Розглянемо алфавіт $\Sigma =\{a,b,c\}$ та мови $L_1,L_2,L_3$ над $\Sigma$. $L_1=\{a,b\}$, $L_2=\{b,c\}$, $L_3=\{ac,ba,bb,ca,cb\}$. Мова $L=((L_1\cdot {\Sigma }^{\ast })\cap ({\Sigma }^{\ast }\cdot L_2))\setminus ({\Sigma }^{\ast }\cdot L_3\cdot {\Sigma }^{\ast })=$ $\{a^{m}b{c}^n:m\ge 0,n\ge 0\}$ є локальною.

Властивості

• Будь-яка локальна мова є автоматною.
• Мова $L$ над алфавітом $\Sigma$, що не містить порожнього слова, є регулярною тоді і лише тоді, коли існують такі алфавіт ${\Sigma }_0$, локальна мова $L_0\subseteq {\Sigma }_0^{\ast }$ і побуквенний гомоморфізм $h:{\Sigma }_0^{\ast }\to {\Sigma }^{\ast }$, що $L=h(L_0)$.
• Для перевірки чи належить слово $w$ локальній мові $L$, достатньо локально переглядати підслова слова $w$ довжиною 2.
• Локальні мови є окремим випадком $k$-тестових мов, з $k=2$ .

Література

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book