Как доказать, что язык не зависит от контекста?

Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым?

Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические методы для поиска контекстно-свободной грамматики для данного языка?

Для регулярных языков, есть являются систематические способы , чтобы получить регулярную грамматику / конечно-автомат: например, Myhill-Nerode теорема дает один из способов. Есть ли соответствующая техника для контекстно-свободных языков?

Моя мотивация здесь состоит в том, чтобы (надеюсь) создать справочный вопрос, который содержит список методов, которые часто бывают полезны при попытке доказать, что данный язык не зависит от контекста. Поскольку у нас есть много вопросов, которые являются частными случаями этого, было бы хорошо, если бы мы могли документировать общий подход или общие приемы, которые можно использовать при решении подобных проблем.

Практический подход, который во многих примерах работает (но не всегда, я знаю), пытается найти структуру вложенности строк в языке. «Вложенные зависимости» должны создаваться одновременно в разных частях строки.

Также у нас есть основной набор инструментов :

1. конкатенация: если вы можете разделить язык на две последовательные части, используйте эту продукцию$S\to S_1S_2$

2. объединение: разделены на непересекающиеся части$S\to S_1 \mid S_2$

3. итерация:$S\to S_1S \mid \varepsilon$

Пример 1

Вот пример для вложения (спасибо Рафаэль).

$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$

Заменить от . Теперь мы можем бросить в условиях.2 l $n$$2l$$n$

Замените на (в замешательстве? это 'oh', а не 'ноль'). Применить инструменты для объединения. Мы работаем с здесь. Также тогда и только тогда, когда и где - новая переменная. Заменить на .k > o  или  k < o o k > o k > o k = s + o s > 0 s k s + $k \neq o$$k > o \text{ or } k < o$$o$$k > o$$k>o$$k=s+o$$s>0$$s$$k$$s+o$

$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$

Несколько простых переписывает.

$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N} \}$

Теперь мы видим структуру вложенности и начинаем строить грамматику.

T → b U U → b U ∣ $S_1 \to TV$ , , (см .: объединение и итерация здесь)$T\to bU$$U\to bU \mid \varepsilon$

o $V \to bVb \mid W$ (мы генерируем 'с обеих сторон)$o$ $b$

$W \to aWaa\mid X$

Y → b c b c Z → b c Z ∣ $X\to YZ$ , ,$Y\to bcbc$$Z\to bcZ\mid \varepsilon$

Пример 2

$K =\{ a^kb^lc^m \mid l=m+k\}$

Первое «очевидное» переписывание.

$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$

В лингвистике это называется «перекрестной последовательной зависимостью»: чередование (обычно) строго указывает на отсутствие контекста. Конечно и мы спасены.m + k = k + $k,m,k,m$$m+k=k+m$

$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$

с производствами , ,X → a X b ∣ ε Y → b Y c ∣ $S\to XY$$X\to aXb\mid \varepsilon$$Y\to bYc\mid \varepsilon$

Точно так же$K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$

с производствами ,X → b X c ∣ $S\to aSc \mid X$$X\to bXc\mid \varepsilon$

Заключительный комментарий: эти методы помогут вам создать кандидатскую контекстно-свободную грамматику, которая, будем надеяться, распознает ваш язык. До сих пор может потребоваться подтверждение правильности , чтобы гарантировать, что грамматика действительно работает для распознавания вашего языка (не более и не менее).

Существует одна характеристика КЛЛ, которая может быть полезна, теорема Хомского-Шютценбергера .

Дейк язык

Пусть алфавит. Определим Дейка -Language из в контекстно-свободная грамматика с заданнымД Т ⊆ ( Т ∪ T ) * T G = ( { S } , Т ∪ T , δ , S ) $T$$D_T \subseteq (T \cup \hat{T})^*$$T$$G = (\{S\}, T \cup \hat{T}, \delta, S)$$\delta$

$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad a \in T$ .

Теорема Хомского-Шютценбергера

$L \subseteq \Sigma^*$ зависит от контекста, если и только если есть

• алфавит ,$T$
• обычный язык и$R \subseteq (T \cup \hat{T})^*$
• гомоморфизм$\psi : (T \cup \hat{T}) \to \Sigma^*$

и что

$\qquad \displaystyle L = \psi(D_T \cap R)$ .

Обратите внимание, что гомоморфизм распространяется на слова (символ за символом), а затем на языки (слово за словом).

пример

Рассмотрим . С$L = \{ a^n b^n c^m \mid n,m \in \mathbb{N}$

• Т = { ] , ⟩ $T = \{ [, \langle\}$ (и, канонически, ),$\hat{T} = \{ ], \rangle\}$
• $R = \mathcal{L}([^* ]^*\langle^* \rangle^*)$ и
• $\psi(x) = \begin{cases} a, &x = [ \\ b, &x =\ ] \\ \varepsilon, &x = \langle \\ c, &x =\ \rangle \end{cases}$

из теоремы следует, что зависит от контекста, в частности, поскольку$L$

$\qquad\displaystyle D_T \cap R = \{[^n ]^n \langle^m \rangle^m \mid n,m \in \mathbb{N}\}$ .

Пример 2

Покажите, что зависит от контекста.$L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \neq o, 2l = n, m \geq 2 \}$

Здесь нам нужен один тип скобок для , один для , один для , а другой используется для моделирования , вызывающего . Мы используем$a$$bc$$b$$b$$k \neq o$

• $T = \{ [, \langle, \vdash, < \}$ ,
• $R = \mathcal{L}(<^+>^+\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*) \cup \mathcal{L}(\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*<^+>^+)$ и
• $\psi(x) = \begin{cases} b, &x \in \{\vdash, \dashv, <\} \\ a, &x = [ \\ aa, &x =\ ] \\ bc, &x = \langle \\ \varepsilon, &\text{else} \end{cases}$

и применить теорему. Чтобы увидеть, что , нам не нужно больше, чем тот факт, что совпадающие символы (например, и ) должны встречаться одинаково часто в любом . Добавляя это противоречие к регулярным выражениям, которые мы определили с помощью , получим$L = \psi(D_T \cap R)$$[$$]$$w \in D_T$$R$

$\qquad \begin{align*} D_T \cap R = &\{<^p>^p \vdash^o [^l \langle^m \rangle^m ]^l \dashv^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2\} \\ &\cup\ \{\dots\} \end{align*}$

и вместе с тем

$\qquad\begin{align*} \psi(D_T \cap R) &= \{ b^{p+o} a^l (bc)^m a^{2l} b^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2 \} \\ &\quad \cup\ \{ \dots \} \\ &= \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k > o, 2l = n, m \geq 2 \} \\&\quad \cup\ \{ \dots \} \\ &= L \;. \end{align*}$

Грамматикам и автоматам

Если мы хотим иметь в конце автомат или грамматику, у нас впереди еще немного работы.

• К автомату, построить NPDA для и НКА для . Первое является стандартным, и у нас есть алгоритмы для второго, при условии, что язык дан в подходящем представлении (см. Также здесь ). Пересечение - это еще одна стандартная конструкция, и можно применять к каждому переходу индивидуально. R $D_T$$R$$\psi$

• Что касается грамматики, постройте одну для (опять же, она должна быть стандартной), возьмите одну для и пересекайте их . Затем примените к набору правил (символ для символа).D T$R$$D_T$$\psi$

Возможно, это легко, так как алгоритмический; сложность заключается в нахождении подходящих , и . Я не знаю, является ли этот подход (часто) более простым, чем непосредственное конструирование КПК / грамматик, но он может позволить сосредоточиться на важных особенностях языка под рукой. Попробуйте сами!R $T$$R$$\psi$