Участник:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 77: Строка 77:
 
{{Теорема
 
{{Теорема
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.  
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.  
То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>
+
То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>
 
|proof =
 
|proof =
  
Строка 87: Строка 87:
 
1. Включаем по правилу <tex> \mathtt{scan}</tex>.<br/>
 
1. Включаем по правилу <tex> \mathtt{scan}</tex>.<br/>
 
Это произошло, если <tex> \alpha = \alpha ' a</tex>, <tex>a = w_{j-1}</tex> и <tex> [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>.<br/>
 
Это произошло, если <tex> \alpha = \alpha ' a</tex>, <tex>a = w_{j-1}</tex> и <tex> [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>.<br/>
По предположению индукции <tex>S \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i...w_{j-2}</tex>,<br/>  
+
По предположению индукции <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i...w_{j-2}</tex>,<br/>  
 
тогда в силу <tex>a = w_{j-1}</tex> получаем <tex>\alpha = \alpha ' a \Rightarrow^* w_i...w_{j-2}w_{j-1} = w_i...w_{j-1}</tex>.<br/>
 
тогда в силу <tex>a = w_{j-1}</tex> получаем <tex>\alpha = \alpha ' a \Rightarrow^* w_i...w_{j-2}w_{j-1} = w_i...w_{j-1}</tex>.<br/>
Таким образом условия: <tex>S \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i...w_{j-1}</tex> выполняются.
+
Таким образом условия: <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i...w_{j-1}</tex> выполняются.
  
 
2. Включаем по правилу <tex> \mathtt{predict}</tex>.<br/>
 
2. Включаем по правилу <tex> \mathtt{predict}</tex>.<br/>
 
По построению: <tex> \alpha = \varepsilon </tex> и <tex>i=j</tex>, что автоматически влечет второй пункт утверждения.<br/>
 
По построению: <tex> \alpha = \varepsilon </tex> и <tex>i=j</tex>, что автоматически влечет второй пункт утверждения.<br/>
Кроме того <tex>\exists  i' \le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i</tex>, из чего по предположению индукции следует <tex>S \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>  
+
Кроме того <tex>\exists  i' \le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i</tex>, из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>  
 
и <tex> \alpha ' \Rightarrow^* w_{i'}...w_{i-1}</tex>.<br/>
 
и <tex> \alpha ' \Rightarrow^* w_{i'}...w_{i-1}</tex>.<br/>
Получаем, что <tex>S \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0...w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S \Rightarrow^* w_0...w_{i'-1} w_{i'}...w_{i-1} A \delta' \delta ''
+
Получаем, что <tex>S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0...w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S' \Rightarrow^* w_0...w_{i'-1} w_{i'}...w_{i-1} A \delta' \delta ''
</tex>, в итоге <tex> S \Rightarrow^* w_0...w_{i-1} A \delta</tex>, что нам и требовалось.
+
</tex>, в итоге <tex> S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, что нам и требовалось.
  
 
3. Включаем по правилу <tex> \mathtt{complete}</tex>.<br/>
 
3. Включаем по правилу <tex> \mathtt{complete}</tex>.<br/>
Строка 103: Строка 103:
  
 
=====<tex>\Longleftarrow</tex>=====
 
=====<tex>\Longleftarrow</tex>=====
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0...w_{i-1} A \delta</tex> из <tex>S</tex> и  <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
+
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0...w_{i-1} A \delta</tex> из <tex>S'</tex> и  <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
 +
индукцию по длине вывода <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
 
Рассмотрим три случая последнего символа <tex>\alpha</tex>:
 
Рассмотрим три случая последнего символа <tex>\alpha</tex>:
  
 
1. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i...w_{j-2}</tex>.<br/>
 
1. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i...w_{j-2}</tex>.<br/>
 
По предположению индукции: <tex>[A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>, а отсюда по правилу <tex> \mathtt{scan}</tex> получаем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>.
 
По предположению индукции: <tex>[A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>, а отсюда по правилу <tex> \mathtt{scan}</tex> получаем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>.
 +
 +
2. <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha ' \Rightarrow^* w_i...w_{i'-1} \wedge B ' \Rightarrow^* w_{i'}...w_{j-1}</tex>.<br/>
 +
Тогда имеем <tex>[A \rightarrow \alpha ' a \cdot  \beta, i] \in D_{j}</tex>. Также можно записать <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0...w_{i-1} w_i...w_{i'-1}B \beta \delta</tex>,
 +
а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}<tex>.<br/>
 +
Применяя индукцию по второму параметру получим <tex>[B \rightarrow \eta \cdot, i'] \in D_j</tex>, откуда по правилу <tex> \mathtt{complete}</tex> получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}</tex>.
 +
 +
3. <tex>\alpha = \varepsilon </tex>, тогда <tex>i=j</tex>.<br/>
 +
Тогда либо <tex>i = 0 \wedge A = S \wedge \delta = \varepsilon</tex>, что доказывает базу индукции,<br/>
 +
либо вывод можно записать в виде <tex>S' \Rightarrow^* w_0...w{i'-1}w_{i'}...w{i-1} A \delta ' \delta '' = w_0...w_{i-1} A \delta</tex> для некоторого правила <tex>(A' \rightarrow w_{i'}...w_{i-1} A \delta ') \in P</tex>. <br/>
 +
Отсюда по предположению индукции <tex>[A' \rightarrow \cdot w_{i'}...w_{i-1} A \delta ', i'] \in D_{i'}</tex>,
 +
что после нескольких применений правила <tex> \mathtt{scan}</tex> приводит к <tex>[A' \rightarrow w_{i'}...w_{i-1} \cdot  A \delta ', i'] \in D_{i}</tex>,
 +
после чего по правилу <tex> \mathtt{predict}</tex> получим <tex>[A \rightarrow \cdot \beta, i] \in D_{j}</tex>, что и требовалось.
  
 
}}
 
}}

Версия 19:21, 18 января 2016

Алгоритм Эрли позволяет определить, выводится ли данное слово [math]w[/math] в данной контекстно-свободной грамматике [math]G[/math].

Вход: КС грамматика [math] G=\langle N,\Sigma, P, S \rangle[/math] и слово [math]w[/math].
Выход: [math]true[/math], если [math]w[/math] выводится в [math]G[/math]; [math]false[/math] — иначе.

Определения

Определение:
Пусть [math]G = \langle N, \Sigma, P, S \rangle[/math]контекстно-свободная грамматика и [math]w = w_1 w_2 ... w_n[/math] — входная цепочка из [math]\Sigma^*[/math]. Объект вида [math][A \rightarrow \alpha \cdot \beta, i][/math], где [math]A \rightarrow \alpha \beta [/math] — правило из [math]P[/math] и [math]0 \leqslant i \leqslant n[/math] — позиция в [math]w[/math], называется ситуацией, относящейся к цепочке [math]w[/math]. [math] \cdot [/math] — вспомогательный символ, который не явлется терминалом или нетерминалом ( [math] \cdot \notin \Sigma \cup N[/math]).


Определение:
[math]j[/math]-м списком ситуаций [math]D_j[/math] для входной цепочки [math]w = w_1 w_2 ... w_n[/math], где [math]0 \leqslant j \leqslant n[/math], называется множество ситуаций [math]\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* w_{i+1} ... w_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* w_1...w_i \rbrace[/math]. То есть [math]\gamma \alpha [/math] выводит часть [math]w[/math] c первого по [math]j[/math]-й символ.


Лемма:
[math](\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow w \in L(G)[/math].
Доказательство:
[math]\triangleright[/math]
Поскольку [math]S \Rightarrow^* \gamma S \delta[/math] (при [math]\gamma = \delta = \varepsilon[/math]), из определения [math]D_n[/math] получаем, что [math]([S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* w_1 ... w_n = w)[/math].
[math]\triangleleft[/math]


Определение:
Последовательность списков ситуаций [math]D_0, D_1, .., D_n[/math] называется списком разбора для входной цепочки [math]w[/math].


Алгоритм Эрли

Чтобы воспользоваться леммой, необходимо найти [math]D_n[/math] для [math]w[/math]. Алгоритм Эрли является динамическим алгоритмом: он последовательно строит список разбора, причём при построении [math]D_j[/math] используются [math]D_0, \ldots, D_{j}[/math] (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).

Алгоритм основывается на следующих трёх правилах:

  1. Если [math][A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}[/math] (где [math]w_j[/math][math]j[/math]-ый символ строки), то [math][A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j[/math].
  2. Если [math][B \rightarrow \eta \cdot, i] \in D_j[/math] и [math][A \rightarrow \alpha \cdot B \beta, k] \in D_i[/math], то [math][A \rightarrow \alpha B \cdot \beta, k] \in D_j[/math].
  3. Если [math][A \rightarrow \alpha \cdot B \beta, i] \in D_{j} [/math] и [math](B \rightarrow \eta) \in P [/math], то [math][B \rightarrow \cdot \eta, j] \in D_{j}[/math].

Псевдокод

Для простоты добавим новый стартовый вспомогательный нетерминал [math]S'[/math] и правило [math](S' \rightarrow S)[/math].

function [math]\mathtt{earley}(G, w)[/math]:
  // Инициализация 
  [math] D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace [/math]
  for i = 1 to len(w) - 1
    [math]D_i[/math] = [math]\varnothing [/math]
  // Вычисление ситуаций 
  for j = 0 to len(w) - 1
    [math]\mathtt{scan}(D, j, G, w)[/math]
    while [math]D_j[/math] изменяется
      [math]\mathtt{complete}(D, j, G, w)[/math]
      [math]\mathtt{predict}(D, j, G, w)[/math]
  // Результат 
  if  [math][S' \rightarrow S \cdot, 0] \in D_{len(w)} [/math]
    return True
  else
    return False    
// Первое правило 
function [math]\mathtt{scan}(D, j, G, w)[/math]:
  if [math]j[/math] == [math]0[/math]
    return
  for [math][A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} [/math]
    if [math]a[/math] == [math]w_{j - 1}[/math]
      [math]D_{j}[/math] [math] \cup[/math]= [math][A \rightarrow \alpha \cdot a \beta, i][/math]

// Второе правило 
function [math]\mathtt{complete}(D, j, G, w)[/math]:
  for [math][B \rightarrow \eta \cdot, i] \in D_{j} [/math]
    for [math][A \rightarrow \alpha \cdot B \beta, k] \in D_{i} [/math]
      [math]D_{j}[/math] [math] \cup[/math]= [math][A \rightarrow \alpha B \cdot \beta, k][/math]
// Третье правило 
function [math]\mathtt{predict}(D, j, G, w)[/math]:
  for [math][A \rightarrow \alpha \cdot B \beta, i] \in D_{j} [/math]
    for [math](B \rightarrow \eta) \in P [/math]
      [math]D_{j}[/math] [math]\cup[/math]= [math][B \rightarrow \cdot \eta, j][/math]

Корректность алгоритма

Теорема:
Приведенный алгоритм правильно строит все списки ситуаций. То есть алгоритм поддерживает инвариант [math] [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})[/math]
Доказательство:
[math]\triangleright[/math]
[math]\Longrightarrow[/math]

Докажем индукцией по исполнению алгоритма.
База — [math][S' \rightarrow \cdot S, 0] \in D_0[/math]. Осталось разобраться, в результате применения какого правила ситуация [math] [A \rightarrow \alpha \cdot \beta, i] [/math] попала в [math]D_{j}[/math]

1. Включаем по правилу [math] \mathtt{scan}[/math].
Это произошло, если [math] \alpha = \alpha ' a[/math], [math]a = w_{j-1}[/math] и [math] [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}[/math].
По предположению индукции [math]S' \Rightarrow^* w_0...w_{i-1} A \delta[/math] и [math]\alpha' \Rightarrow^* w_i...w_{j-2}[/math],
тогда в силу [math]a = w_{j-1}[/math] получаем [math]\alpha = \alpha ' a \Rightarrow^* w_i...w_{j-2}w_{j-1} = w_i...w_{j-1}[/math].
Таким образом условия: [math]S' \Rightarrow^* w_0...w_{i-1} A \delta[/math] и [math]\alpha \Rightarrow^* w_i...w_{j-1}[/math] выполняются.

2. Включаем по правилу [math] \mathtt{predict}[/math].
По построению: [math] \alpha = \varepsilon [/math] и [math]i=j[/math], что автоматически влечет второй пункт утверждения.
Кроме того [math]\exists i' \le i[/math] и ситуация [math][A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i[/math], из чего по предположению индукции следует [math]S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''[/math] и [math] \alpha ' \Rightarrow^* w_{i'}...w_{i-1}[/math].
Получаем, что [math]S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''[/math], значит [math]S \Rightarrow^* w_0...w_{i'-1} \alpha' A \delta' \delta '' [/math], следовательно [math] S' \Rightarrow^* w_0...w_{i'-1} w_{i'}...w_{i-1} A \delta' \delta '' [/math], в итоге [math] S' \Rightarrow^* w_0...w_{i-1} A \delta[/math], что нам и требовалось.

3. Включаем по правилу [math] \mathtt{complete}[/math].
По построению: [math] \alpha = \alpha ' A' [/math] и [math]\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j[/math].
Cледовательно [math]\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}[/math], что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.

[math]\Longleftarrow[/math]

В обратную сторону будем доказывать индукцией по суммарной длине вывода [math]w_0...w_{i-1} A \delta[/math] из [math]S'[/math] и [math]w_i...w_{j-1}[/math] из [math]\alpha[/math]. После чего применим индукцию по длине вывода [math]w_i...w_{j-1}[/math] из [math]\alpha[/math].
Рассмотрим три случая последнего символа [math]\alpha[/math]:

1. [math]\alpha = \alpha ' a[/math], тогда [math]a = w_{j-1}[/math] и [math]\alpha ' \Rightarrow^* w_i...w_{j-2}[/math].
По предположению индукции: [math][A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}[/math], а отсюда по правилу [math] \mathtt{scan}[/math] получаем [math][A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}[/math].

2. [math]\alpha = \alpha ' B[/math], тогда [math]\exists i' : \alpha ' \Rightarrow^* w_i...w_{i'-1} \wedge B ' \Rightarrow^* w_{i'}...w_{j-1}[/math].
Тогда имеем [math][A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}[/math]. Также можно записать [math]S' \Rightarrow^* w_0...w_{i-1} A \delta[/math], как [math]S' \Rightarrow^* w_0...w_{i-1} w_i...w_{i'-1}B \beta \delta[/math], а также [math]B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}\lt tex\gt .\lt br/\gt Применяя индукцию по второму параметру получим \lt tex\gt [B \rightarrow \eta \cdot, i'] \in D_j[/math], откуда по правилу [math] \mathtt{complete}[/math] получаем [math][A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}[/math].

3. [math]\alpha = \varepsilon [/math], тогда [math]i=j[/math].
Тогда либо [math]i = 0 \wedge A = S \wedge \delta = \varepsilon[/math], что доказывает базу индукции,
либо вывод можно записать в виде [math]S' \Rightarrow^* w_0...w{i'-1}w_{i'}...w{i-1} A \delta ' \delta '' = w_0...w_{i-1} A \delta[/math] для некоторого правила [math](A' \rightarrow w_{i'}...w_{i-1} A \delta ') \in P[/math].
Отсюда по предположению индукции [math][A' \rightarrow \cdot w_{i'}...w_{i-1} A \delta ', i'] \in D_{i'}[/math], что после нескольких применений правила [math] \mathtt{scan}[/math] приводит к [math][A' \rightarrow w_{i'}...w_{i-1} \cdot A \delta ', i'] \in D_{i}[/math],

после чего по правилу [math] \mathtt{predict}[/math] получим [math][A \rightarrow \cdot \beta, i] \in D_{j}[/math], что и требовалось.
[math]\triangleleft[/math]

Пример

Построим список разбора для строки [math]w = (a + a)[/math] в грамматике со следующими правилами:

  • [math]S \rightarrow T + S[/math];
  • [math]S \rightarrow T [/math];
  • [math]T \rightarrow F * T[/math];
  • [math]T \rightarrow F[/math];
  • [math]F \rightarrow ( S )[/math];
  • [math]F \rightarrow a[/math].
[math]I_0[/math]
Ситуация Из правила
[math][S' \rightarrow \cdot S, 0][/math] 0
[math][S \rightarrow \cdot T + S, 0][/math] 3
[math][S \rightarrow \cdot T, 0][/math] 3
[math][T \rightarrow \cdot F * T, 0][/math] 3
[math][T \rightarrow \cdot F, 0][/math] 3
[math][F \rightarrow \cdot ( S ), 0][/math] 3
[math][F \rightarrow \cdot a, 0][/math] 3
[math]I_1[/math]
Ситуация Из правила
[math][F \rightarrow ( \cdot S ), 0][/math] 1
[math][S \rightarrow \cdot T + S, 1][/math] 3
[math][S \rightarrow \cdot T, 1][/math] 3
[math][T \rightarrow \cdot F * T, 1][/math] 3
[math][T \rightarrow \cdot F, 1][/math] 3
[math][F \rightarrow \cdot ( S ), 1][/math] 3
[math][F \rightarrow \cdot a, 1][/math] 3
[math]I_2[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot, 1][/math] 1
[math][T \rightarrow F \cdot * T, 1][/math] 2
[math][T \rightarrow F \cdot , 1][/math] 2
[math][S \rightarrow T \cdot , 1][/math] 2
[math][S \rightarrow T \cdot + S, 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]I_3[/math]
Ситуация Из правила
[math][S \rightarrow T + \cdot S, 1][/math] 1
[math][S \rightarrow \cdot T + S, 3][/math] 3
[math][S \rightarrow \cdot T, 3][/math] 3
[math][T \rightarrow \cdot F * T, 3][/math] 3
[math][T \rightarrow \cdot F, 3][/math] 3
[math][F \rightarrow \cdot ( S ), 3][/math] 3
[math][F \rightarrow \cdot a, 3][/math] 3
[math]I_4[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot , 3][/math] 1
[math][T \rightarrow F \cdot * T, 3][/math] 2
[math][T \rightarrow F \cdot , 3][/math] 2
[math][S \rightarrow T \cdot + S, 3][/math] 2
[math][S \rightarrow T \cdot , 3][/math] 2
[math][S \rightarrow T + S \cdot , 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]I_5[/math]
Ситуация Из правила
[math][F \rightarrow ( S )\cdot , 0][/math] 1
[math][T \rightarrow F \cdot * T, 0][/math] 2
[math][T \rightarrow F \cdot , 0][/math] 2
[math][S \rightarrow T \cdot + S, 0][/math] 2
[math][S \rightarrow T \cdot , 0][/math] 2
[math][S' \rightarrow S \cdot , 0][/math] 2

Так как [math][S' \rightarrow S \cdot , 0] \in I_5[/math], то [math]w \in L(G) [/math].

Источники информации

  • Алексей Сорокин — Алгоритм Эрли
  • Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.