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

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

Визначення

Мова $L\subseteq \Sigma ^{*}$ над алфавітом $\Sigma$ називається локальною, якщо існують такі мови $L_{1}\subseteq \Sigma ^{*}$,$L_{2}\subseteq \Sigma ^{*}$ та $L_{3}\subseteq \Sigma ^{*}$, що

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

Приклади

• Розглянемо алфавіт $\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 ^{*})\cap (\Sigma ^{*}\cdot L_{2}))\setminus (\Sigma ^{*}\cdot L_{3}\cdot \Sigma ^{*})=$ $\{a^{m}bc^{n}:m\geq 0,n\geq 0\}$ є локальною.

Властивості

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

Література

• Mark V. Lawson (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• Robert McNaughton (1971). Counter-free Automata. Research Monograph. Т. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
• Jacques Sakarovitch (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Саломаа, Арто (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064.