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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(→‎Псевдокод)
Строка 76: Строка 76:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
−
<tex>a_1...a_n</tex> - входная строка. <tex>A_1...A_m</tex> - нетерминалы.
+
<tex>a</tex> - входная строка. <tex>A</tex> - нетерминалы.
 
<tex>P[i,j,k] = true</tex> если есть продукция <tex>A_i \Rightarrow A_j A_k</tex>.
 
<tex>P[i,j,k] = true</tex> если есть продукция <tex>A_i \Rightarrow A_j A_k</tex>.
−
<tex>S(i,c) = true</tex> если есть продукция <tex>A_i \Rightarrow c</tex> (где <tex>c</tex> - терминал).
+
<tex>S[i,j] = true</tex> если есть продукция <tex>A_i \Rightarrow a_j</tex>.
−
<tex>d[i][j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.
+
<tex>d[i,j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.
 +
Считаем, что <tex>A_0</tex> - стартовый нетерминал.
  
−
   for i = 1 to m
+
   function CYK (a: array [1..n] of char, P: array [1..m,1..m,1..m] of bool, S: array []) : bool
−
    for j = 1 to n
+
  var d: array [1..m,1..n,1..n] of bool
−
      d[i][j,j] = S(i,a[j])
+
  begin
 +
    for i = 1 to m
 +
      for j = 1 to n
 +
        d[i,j,j] = S[i,j]
  
−
  for l = 2 to n
+
    for l = 2 to n
−
    for i = 1 to n+1-l
+
      for i = 1 to n+1-l
−
      for j = 1 to m
+
        for j = 1 to m
−
        d[j][i,i+l-1] = false
+
          d[j,i,i+l-1] = false
−
        for k = i to i+j-2
+
          for k = i to i+j-2
−
          d[j][i,i+l-1] = d[j][i,i+l-1] or (d[j][i,k] and d[j][k+1,i+l-1])
+
            d[j,i,i+l-1] = d[j,i,i+l-1] or (d[j,i,k] and d[j,k+1,i+l-1])
 +
    result = d[0,1,n]
 +
  end
  
 
= Ссылки =
 
= Ссылки =

Версия 05:18, 26 декабря 2011

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

Определения

Формальная грамматика

Формальная грамматика - способ описания формального языка, то есть некоторого подмножества слов данного конечного алфавита. Выделяют порождающие грамматики, состоящие из следующих компонентов:

  1. Множество терминальных символов (терминалов) - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.
  2. Множество нетерминальных символов (нетерминалов) - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).
  3. Множество правил вывода (продукций) - правил вида L → R, где:
    1. L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.
    2. R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.
  4. S - стартовый нетерминал.

Выводом называется последовательность строк из терминалов и нетерминалов, такая, что:

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

Существование в грамматике вывода для получения конкретного слова - критерий принадлежности слова языку, определяемому грамматикой.

Пример

Терминалы: {a, b}. Нетерминалы: {S, A, B}. Продукции:

  • S → AB
  • A → AB
  • AB → ba
  • A → a
  • B → b

Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, ...

Слова, невыводимые в данной грамматике: a, b, baa, baba, ...

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

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминал, а R - последовательность терминалов и нетерминалов.

Пример

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

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

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

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

Нормальная форма Хомского

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

  • 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]O(n^3)[/math] (где [math]n[/math] - длина строки) и требует [math]O(n^2)[/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]a[/math] - входная строка. [math]A[/math] - нетерминалы. [math]P[i,j,k] = true[/math] если есть продукция [math]A_i \Rightarrow A_j A_k[/math]. [math]S[i,j] = true[/math] если есть продукция [math]A_i \Rightarrow a_j[/math]. [math]d[i,j,k][/math] - можно ли вывести из нетерминала [math]A_i[/math] подстроку [math]a_j...a_k[/math]. Считаем, что [math]A_0[/math] - стартовый нетерминал. 

 function CYK (a: array [1..n] of char, P: array [1..m,1..m,1..m] of bool, S: array []) : bool
 var d: array [1..m,1..n,1..n] of bool
 begin
   for i = 1 to m
     for j = 1 to n
       d[i,j,j] = S[i,j]

   for l = 2 to n
     for i = 1 to n+1-l
       for j = 1 to m
         d[j,i,i+l-1] = false
         for k = i to i+j-2
           d[j,i,i+l-1] = d[j,i,i+l-1] or (d[j,i,k] and d[j,k+1,i+l-1])
   result = d[0,1,n]
 end

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_выводе_в_контекстно-свободной_грамматике,_алгоритм_Кока-Янгера-Касами&oldid=15236»