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

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

Визначення

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

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

Приклади

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

Властивості

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

Література

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