CYK алгоритм путаницы псевдокодов

Question

Так что я читал об алгоритме CYK в википедии и во многих powerpoints/pdfs.

В википедии есть часть, где я не на 100% говорю то, что пытаюсь сказать. Можете ли вы, ребята, сломать это для меня?

let the input be a string S consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
for each i = 1 to n
  for each unit production Rj -> ai
     set P[i,1,j] = true

for each i = 2 to n -- Length of span
 for each j = 1 to n-i+1 -- Start of span
  for each k = 1 to i-1 -- Partition of span
   for each production RA -> RB RC
    if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true

if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then S is member of language
  else
S is not member of language

Часть, которая действительно смущает меня: "если любое из P[1,n,x] истинно (x итерируется по множеству s, где s все индексы для Rs), то S является членом языка, иначе S не является членом языка "

Говорится ли для любых n и x, что существует, если это правда, то это член? или это говорит для длины строки n и x, если это правда, то это член? или что то совсем другое?

И что именно X?

Редактировать:

Спасибо, ребята, я определенно научился это делать. Хотел бы я получить оба ваших ответа в качестве выбранного ответа.

Answer 1

Когда вы выполняете алгоритм CYK, вы в основном заполняете нижнюю треугольную матрицу от ее нижнего до самого верхнего элемента. Всякий раз, когда какой-то элемент (j,i,x) где j индекс столбца, i это индекс строки и x если нетерминальный символ равен true, это означает, что вы можете сгенерировать подпоследовательность j в j+i-1 твоего слова из символа Rx,

Ваша цель - сгенерировать все слово из одного из начальных символов. Элемент, соответствующий возможности генерации всего слова, (1,n,x) - самый левый и самый верхний элемент матрицы, где x это индекс вашего нетерминального символа. Поскольку вы должны начать с одного из стартовых символов, вы ищете только подмножество всех ваших нетерминалов - подмножество s, Если вам удается сгенерировать все слово из одного из начальных символов, вы просто утверждаете, что это слово является частью языка. Если такого начального символа не существует, вы не можете сгенерировать это слово, и это слово не является частью языка, описанного грамматикой.

Answer 2

Это говорит о том, что если P[1,n,x] истинно для любого начального нетерминала x, то существует синтаксический анализ всей строки (лексических токенов от 1 до n) как нетерминала x. В этом алгоритме P[a,b,c] = true означает, что подстрока лексических токенов, начинающаяся с индекса a и имеющая длину b, может быть проанализирована как нетерминальная c.