Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Контекстно-свободная грамматика == Для того, чтобы определить контекстно-свободную грам…»)
 
 
(не показано 35 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
#перенаправление [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 +
'''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий эту задачу.
 +
 +
= Определения =
 +
 
== Контекстно-свободная грамматика ==
 
== Контекстно-свободная грамматика ==
  
Для того, чтобы определить контекстно-свободную грамматику, необходимо:
+
{{Определение
1) Задать конечное множество A - алфавит; его
+
|definition=
элементы  называют символами, а конечные последовательности симво-
+
'''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — способ описания формального языка, задающийся:
лов называют словами (в данном алфавите);
+
 
2) Разделить все символы алфавита A на две группы: терми-
+
* Множеством <tex>\Sigma</tex> терминальных символов
нальные ("окончательные") и нетерминальные ("промежуточные");
+
* Множеством <tex>N</tex> нетерминальных символов
3) Выбрать один из нетерминальных символов, который будет считаться начальным;
+
* Стартовым нетерминалом <tex>S \in N</tex>
4) Указать конечное число правил грамматики вида
+
* Множеством продукций вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части - одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.
    K -> X
+
}}
где K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов.
+
 
Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.
+
=== Пример ===
 +
 
 +
Терминалы: {(, )}. Нетерминалы: {S}. Продукции:
 +
* S &rarr; SS
 +
* S &rarr; ()
 +
* S &rarr; (S)
 +
 
 +
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом:
 +
* <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex>
 +
 
 +
== Нормальная форма Хомского ==
 +
 
 +
'''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид:
 +
* A &rarr; a, где ''A'' - нетерминал, а ''a'' - терминал
 +
* A &rarr; BC, где ''A'', ''B'', ''C'' - нетерминалы, причем ''B'' и ''C'' не являются начальными нетерминалами
 +
* S &rarr; ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
 +
 
 +
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского.
 +
 
 +
= Алгоритм Кока-Янгера-Касами =
 +
'''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
 +
 
 +
Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, и  <tex>d[A,i,j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} ... a_j</tex>. Тогда:
 +
* <tex>d[A,i,i] = true</tex>, если в грамматике присутствует правило <tex>A \rightarrow a_i</tex>, иначе <tex>false</tex>
 +
* Остальные элементы массива заполняются динамически: <tex>d[A,i,j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B,i,k] \wedge d[C,k+1,j]</tex>. То есть, подстроку <tex>a_i...a_j</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>a_i...a_k</tex> выводима из <tex>B</tex>, а подстрока <tex>a_{k+1}...a_j</tex> - из <tex>C</tex>.
 +
 
 +
Значение <tex>d[S,1,n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике.
 +
 
 +
Заметим, что если массив будет хранить целые числа, а формулу заменить на <tex>d[A,i,j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B,i,k] \cdot d[C,k+1,j]</tex>, то <tex>d[A,i,j]</tex> - количество способов получить подстроку <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
 +
 
 +
Пусть <tex>P_{A \rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,i,j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B,i,k] + d[C,k+1,j] + P_{A \rightarrow BC} )</tex>, то <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
 +
 
 +
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
 +
 
 +
=== Сложность алгоритма ===
 +
 
 +
Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
 +
 
 +
Обработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.
 +
 
 +
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>.
 +
 
 +
Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>.
 +
 
 +
=== Псевдокод ===
 +
 
 +
  function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool
 +
  begin
 +
    d : array [1..m,1..n,1..n] of bool
 +
    for i = 1 to n
 +
      if (A -> a[i] - продукция)
 +
        d[A,i,i] = true
 +
    for len = 1 to n-1
 +
      for i = 1 to n-l
 +
        for (A -> BC - продукция)
 +
          for k = i to i+len-1
 +
            d[A,i,i+len] = d[A,i,i+len] or (d[B,i,k] and d[C,k+1,i+len])
 +
    return d[S,1,n]
 +
  end
 +
 
 +
= Ссылки =
 +
 
 +
* [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm]
 +
* [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами]
  
== Формулировка задачи. ==
+
[[Категория:В разработке]]
+
[[Категория:Дискретная математика и алгоритмы]]
Задача вывода в контекстно-свободной грамматике состоит в поиске алгоритма, проверяющего, можно ли вывести данное слово в этой КС-грамматике.
+
[[Категория:Динамическое программирование]]
 +
[[Категория:Теория формальных языков]]

Текущая версия на 23:24, 4 ноября 2014

Задача о выводе в контекстно-свободной грамматике - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. Алгоритм Кока-Янгера-Касами - алгоритм, решающий эту задачу.

Определения[править]

Контекстно-свободная грамматика[править]

Определение:
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, задающийся:
  • Множеством [math]\Sigma[/math] терминальных символов
  • Множеством [math]N[/math] нетерминальных символов
  • Стартовым нетерминалом [math]S \in N[/math]
  • Множеством продукций вида [math]A \rightarrow B_1 B_2 ... B_n[/math], где [math]A \in N[/math], [math]B_i \in \Sigma \cup N[/math], то есть у которых левые части - одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.


Пример[править]

Терминалы: {(, )}. Нетерминалы: {S}. Продукции:

  • S → SS
  • S → ()
  • S → (S)

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

  • [math] S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) [/math]

Нормальная форма Хомского[править]

Нормальная форма Хомского - нормальная форма КС-грамматик, в которой все продукции имеют вид:

  • A → a, где A - нетерминал, а a - терминал
  • A → BC, где A, B, C - нетерминалы, причем B и C не являются начальными нетерминалами
  • S → ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.

Алгоритм Кока-Янгера-Касами[править]

Алгоритм Кока-Янгера-Касами (Cocke — Younger — Kasami algorithm, CYK - алгоритм) - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.

Пусть дана строка [math]a_1 a_2 ... a_n[/math]. Заведем трехмерный массив d, состоящий из логических значений, и [math]d[A,i,j] = true[/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]a_i a_{i+1} ... a_j[/math]. Тогда:

  • [math]d[A,i,i] = true[/math], если в грамматике присутствует правило [math]A \rightarrow a_i[/math], иначе [math]false[/math]
  • Остальные элементы массива заполняются динамически: [math]d[A,i,j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B,i,k] \wedge d[C,k+1,j][/math]. То есть, подстроку [math]a_i...a_j[/math] можно вывести из нетерминала [math]A[/math], если существует продукция [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]a_i...a_k[/math] выводима из [math]B[/math], а подстрока [math]a_{k+1}...a_j[/math] - из [math]C[/math].

Значение [math]d[S,1,n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике.

Заметим, что если массив будет хранить целые числа, а формулу заменить на [math]d[A,i,j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B,i,k] \cdot d[C,k+1,j][/math], то [math]d[A,i,j][/math] - количество способов получить подстроку [math]a_i...a_j[/math] из нетерминала [math]A[/math].

Пусть [math]P_{A \rightarrow BC}[/math] - стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]d[A,i,j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,j] + P_{A \rightarrow BC} )[/math], то [math]d[A,i,j][/math] - минимальная стоимость вывода подстроки [math]a_i...a_j[/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.

Сложность алгоритма[править]

Пусть, [math]n[/math] - длина входной строки, а [math]m[/math] - количество правил вывода в грамматике.

Обработка правил вида [math]A \rightarrow a_i[/math] выполняется за [math]O(nm)[/math].

Проход по всем подстрокам выполняется за [math]O(n^2)[/math]. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(nm)[/math]. В итоге - [math]O(n^3 m)[/math].

Следовательно, общее время работы алгоритма - [math]O(n^3 m)[/math]. Кроме того, алгоритму требуется память (на массив [math]d[/math]) объемом [math]O(n^2 m)[/math].

Псевдокод[править]

 function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool
 begin
   d : array [1..m,1..n,1..n] of bool
   for i = 1 to n
     if (A -> a[i] - продукция)
       d[A,i,i] = true
   for len = 1 to n-1
     for i = 1 to n-l
       for (A -> BC - продукция)
         for k = i to i+len-1
           d[A,i,i+len] = d[A,i,i+len] or (d[B,i,k] and d[C,k+1,i+len])
   return d[S,1,n]
 end

Ссылки[править]