ТМВ-2020-Семинар-03.03.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Алгоритм Кока–Янгера–Касами

Алгоритм Кока–Янгера–Касами (КЯК) помогает определить выводимо ли заданное слово в заданной контекстно-свободной грамматике, представленной в нормальной форму по Хомскому. Подробнее об алгоритме в лекции 3. Рассмотрим работу данного алгоритма на следующих примерах.

Пример

Выводимо ли слово \(baaba\) в грамматике \(G\), представленной в НФ:
\( S \to AB \mid BC \\ A \to BA \mid a \\ B \to CC \mid b \\ C \to AB \mid a \)

Решение \(\require{cancel}\)

Строим таблицу, в ячейках которой будут нетерминалы, из которых выводится подстроки длины $$\mathbf{i}$$, начиная с \(j\)-го элемента слова.
Следующие подстроки длины $$\mathbf{1}$$ выводятся из соответствующих нетерминалов:
\( \begin{array}{ll} \mathbf{b}\colon & B \\ \mathbf{a}\colon & A, C \end{array} \)

Теперь посмотрим выводы подстрок длины $$\mathbf{2}$$:

\( \begin{array}{ll} \mathbf{ba}\colon & BA \leftarrow A \\ & BC \leftarrow S\\ \mathbf{aa}\colon & \cancel{AA} \\ & \cancel{AC} \\ & \cancel{CA} \\ & CC \leftarrow B \\ \mathbf{ab}\colon & AB \leftarrow S, C \\ & \cancel{CB} \end{array} \)

Продолжаем построение таблицы, определяя нетерминалы, из которых выводятся подстроки длин $$\mathbf{3, 4, 5}$$.

\( \begin{array}{lll} \hline l=\mathbf{3} & & \\ \hline \mathbf{baa}\colon & \mathbf{b}\cdot \mathbf{aa} & \cancel{BB} \\ & \mathbf{ba}\cdot \mathbf{a} & \cancel{AA} \\ & & \cancel{AC} \\ & & \cancel{SA} \\ & & \cancel{SC} \\ \hline \mathbf{aab}\colon & \mathbf{a}\cdot \mathbf{ab} & \cancel{AS} \\ & & \cancel{CS} \\ & & \cancel{AC} \\ & & CC \leftarrow B \\ & \mathbf{aa}\cdot \mathbf{b} & \cancel{BB} \\ \hline \mathbf{aba}\colon & \mathbf{a}\cdot \mathbf{ba} & \cancel{AA} \\ & & \cancel{CA} \\ & & \cancel{AS} \\ & & \cancel{CS} \\ & \mathbf{ab}\cdot \mathbf{a} \\ & & \cancel{SA} \\ & & \cancel{CA} \\ & & \cancel{SC} \\ & & CC \leftarrow{B} \\ \hline \end{array} \) \( \begin{array}{lll} \hline l=\mathbf{4} & & \\ \hline \mathbf{baab}\colon & \mathbf{b}\cdot \mathbf{aab} & \cancel{BB} \\ & \mathbf{ba}\cdot \mathbf{ab} & \cancel{AS} \\ & & \cancel{AC} \\ & & \cancel{SS} \\ & & \cancel{SC} \\ & \mathbf{baa}\cdot \mathbf{b} & — \\ \mathbf{aaba}\colon & \mathbf{a}\cdot \mathbf{aba} & AB \leftarrow S,C \\ & & \cancel{CB} \\ & \mathbf{aa}\cdot \mathbf{ba} & BA \leftarrow A \\ & & \cancel{BS} \\ & \mathbf{aab}\cdot \mathbf{a} & BA \leftarrow A \\ & & BC \leftarrow S \\ \hline \end{array} \) \( \begin{array}{lll} \hline l=\mathbf{5} & & \\ \hline \mathbf{baaba}\colon & \mathbf{b}\cdot \mathbf{aaba} & \cancel{BS} \\ & & BA \leftarrow A \\ & & BC \leftarrow S \\ & \mathbf{ba}\cdot \mathbf{aba} & AB \leftarrow S, C \\ & & \cancel{SB} \\ & \mathbf{baa}\cdot \mathbf{ba} & — \\ & \mathbf{baab}\cdot \mathbf{a} & — \\ \hline \end{array} \)


Таким образом, наша таблица примет следующий вид:
\( \begin{array}{r|ccccc} \mathbf{5} & S,A,C & & & & \\ \mathbf{4} & — & S,A,C & & & \\ \mathbf{3} & — & B & B & & \\ \mathbf{2} & S,A & B & S, C & S, A & \\ \mathbf{1} & B & A,C & A,C & B & A,C \\ \hline & \mathbf{b} & \mathbf{a} & \mathbf{a} & \mathbf{b} & \mathbf{a} \\ \end{array} \)

На вершине таблицы присутствует аксиома (стартовый нетерминал) \(S\). Следовательно, $$baaba \in L(G)$$.

Задача 1

Дана грамматика \(G\):
\( S \to AS \mid b \\ A \to SA \mid a \)

Верно ли, что \(bbaab \in L(G)\)?

Решение

Как в примере определяем нетерминалы, из которых выводятся подстроки длин $$\mathbf{1}–\mathbf{5}$$.

\( \require{cancel} \begin{array}{ll} \hline l=\mathbf{1} & \\ \hline \mathbf{b}\colon & S \\ \mathbf{a}\colon & A \\ \hline l=\mathbf{2} & \\ \hline \mathbf{bb}\colon & \cancel{SS} \\ \mathbf{ba}\colon & SA \leftarrow A \\ \mathbf{aa}\colon & \cancel{AA} \\ \mathbf{ab}\colon & AS \leftarrow S \\ \hline \end{array} \) \( \begin{array}{lll} \hline l=\mathbf{3} & & \\ \hline \mathbf{bba}\colon & \mathbf{bb}\cdot \mathbf{a} & — \\ & \mathbf{b}\cdot \mathbf{ba} & SA \leftarrow A \\ \hline \mathbf{baa}\colon & \mathbf{ba}\cdot \mathbf{a} & \cancel{AA} \\ & \mathbf{b}\cdot \mathbf{aa} & — \\ \hline \mathbf{aab}\colon & \mathbf{aa}\cdot \mathbf{b} & — \\ & \mathbf{a}\cdot \mathbf{ab} & AS \leftarrow S \\ \hline \end{array} \) \( \begin{array}{lll} \hline l=\mathbf{4} & & \\ \hline \mathbf{bbaa}\colon & \mathbf{b}\cdot \mathbf{baa} & — \\ & \mathbf{bb}\cdot \mathbf{aa} & — \\ & \mathbf{bba}\cdot \mathbf{a} & \cancel{AA} \\ \hline \mathbf{baab}\colon & \mathbf{b}\cdot \mathbf{aab} & \cancel{SS} \\ & \mathbf{ba}\cdot \mathbf{ab} & AS \leftarrow S \\ & \mathbf{baa}\cdot \mathbf{b} & — \\ \hline \end{array} \) \( \begin{array}{lll} \hline l=\mathbf{5} & & \\ \hline \mathbf{bbaab}\colon & \mathbf{b}\cdot \mathbf{baab} & \cancel{SS} \\ & \mathbf{bb}\cdot \mathbf{aab} & — \\ & \mathbf{bba}\cdot \mathbf{ab} & AS \leftarrow S \\ & \mathbf{bbaa}\cdot \mathbf{b} & — \\ \hline \end{array} \)

Таблица принимает вид:
\( \begin{array}{r|ccccc} \mathbf{5} & S & & & & \\ \mathbf{4} & — & S & & & \\ \mathbf{3} & A & — & S & & \\ \mathbf{2} & — & A & — & S & \\ \mathbf{1} & S & S & A & A & S \\ \hline & \mathbf{b} & \mathbf{b} & \mathbf{a} & \mathbf{a} & \mathbf{b} \\ \end{array} \)

\(S\) на вершине таблицы $$\Rightarrow bbaab \in L(G)$$.

Лемма о разрастании для контекстно-свободных языков

Формулировка

Если \(L\) — контекстно-свободный язык, тогда \(\exists k\colon k \geqslant 1\) такое, что \(\forall s \in L \:\: \lvert s \rvert \geqslant k \Rightarrow s = uvwxy\) (слово \(s\) можно разбить на пять частей) т. о., что

  • \(\lvert vx \rvert > 0\)
  • \(\lvert vwx \rvert \leqslant k\)
  • \(\forall i \in \mathbb{N_0} \:\: {uv^iwx^iy} \in L\)

Применение леммы к определению контекстно-свободности языка

Пример

Показать, что язык \(L=\{{a^nb^nc^n}\mid n\in \mathbb{N_0}\}\) не является контекстно-свободным.

Доказательство

Пусть язык является контекстно-свободным. Тогда пусть \(k\) — константа из этой леммы. Рассмотрим слово \(s={a^kb^kc^k}\) (\(\lvert s \rvert > k\). Попробуем построить разбиение для этого слова, удовлетворяющее трём условиям леммы.
Рассмотрим следующее разбиение:
\(u=a^{k-1} \;\;\; v=ab \;\;\; w=b^{k-1} \;\;\; x=c \;\;\; y=c^{k-1}\)
При таком разбиении \(\lvert vx \rvert > 0\), \(\forall i \in \mathbb{N_0} \:\: {uv^iwx^iy} \in L \;(i=0\colon {a^{k-1}b^{k-1}c^{k-1}},\; i=1\colon {a^{k}b^{k}c^{k}},\; i=2\colon {a^{k+1}b^{k+1}c^{k+1}}\:\text{и т. д.})\), но \(\lvert vwx \rvert = \lvert {abb^{k-1}c} \rvert = k+2 \not \leqslant k\).

Далее можно показать, что, строя другие разбиения, либо не будет выполняться третье условие (неравномерное разрастание), либо не будет выполняться второе ограничение из условия леммы.

Задача 1

Является ли язык \(L=\{{a^mb^mc^j}\mid m,j \geqslant 1, j < m\}\) контекстно-свободным?

Решение

Пусть язык является контекстно-свободным. Тогда пусть \(k\) — константа из этой леммы. Рассмотрим слово \(s={a^kb^kc^{k-1}}\) (\(\lvert s \rvert > k)\). Попробуем построить разбиение для этого слова, удовлетворяющее трём условиям леммы.
Рассмотрим следующее разбиение:
\(u=a^{k-1} \;\;\; v=a \;\;\; w=\varepsilon \;\;\; x=b \;\;\; y=b^{k-1}c^{k-1}\)

При таком разбиении не будет выполняться третье условие при \(i = 0\) не выполняется \(({a^{k-1}b^{k-1}c^{k-1}} \not \in L)\).

Далее можно показать, что, строя другие разбиения, либо не будет выполняться третье условие (неравномерное разрастание), либо не будет выполняться второе ограничение из условия леммы. Следовательно, язык не является контекстно-свободным.

Задача 2

Является ли язык \(L=\{{a^ib^jc^k}\mid i,j,k \geqslant 1, i < j < k\}\) контекстно-свободным?

Решение

Пусть язык является контекстно-свободным. Тогда пусть \(k\) — константа из этой леммы. Рассмотрим слово \(s={a^{k-2}b^{k-1}kc^{k}}\) (\(\lvert s \rvert > k)\). Попробуем построить разбиение для этого слова, удовлетворяющее трём условиям леммы.
Рассмотрим следующее разбиение:
\(u=a^{k-3} \;\;\; v=ab \;\;\; w=b^{k-2} \;\;\; x=c \;\;\; y=c^{k-1}\)

При таком разбиении выполняются 1 и 3 условия, но \(\lvert vwx \rvert = \lvert {abb^{k-2}c} \rvert = k + 1 \not \geqslant k\)

Строя разбиения, удовлетворяющие 1 и 2 условиям, получим невыполнение 3 условия о равномерном разрастании. Удовлетворяя 2 и 3 условиям, получим невыполнение 1 условия. Таким образом, можно сделать вывод, что язык не является контекстно-свободным.