Редактирование: Алгоритм Эрли

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 7: Строка 7:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 \ldots w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
+
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 ... w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
 
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
 
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
 
}}
 
}}
Строка 13: Строка 13:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Ситуации хранятся в множествах <tex>D_0, \ldots ,D_{n-1}</tex>, называемых '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что  
+
Ситуации хранятся в множествах <tex>D_0,...,D_{n-1}</tex>, называемых '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что  
<tex>\exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta) \wedge A \Rightarrow^* w_i \ldots w_{j-1})</tex>.
+
<tex>\exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Последовательность списков ситуаций <tex>D_0, D_1, \ldots, D_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
+
Последовательность списков ситуаций <tex>D_0, D_1, .., D_{n-1}</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
 
}}
 
}}
  
Строка 27: Строка 27:
 
Алгоритм основывается на следующих трёх правилах:
 
Алгоритм основывается на следующих трёх правилах:
 
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
 
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
# Если <tex>[B \rightarrow \eta \ \cdot, i] \in D_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, k] \in D_j</tex>.
+
# Если <tex>[B \rightarrow \eta \cdot, i] \in D_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, k] \in D_j</tex>.
# Если <tex>[A \rightarrow \alpha \ \cdot B \beta, i] \in D_{j} </tex> и <tex>(B \rightarrow \eta) \in P </tex>, то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}</tex>.
+
# Если <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex> и <tex>(B \rightarrow \eta) \in P </tex>, то <tex>[B \rightarrow \cdot \eta, j] \in D_{j}</tex>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
Строка 35: Строка 35:
 
  '''function''' <tex>\mathtt{earley}(G, w)</tex>:
 
  '''function''' <tex>\mathtt{earley}(G, w)</tex>:
 
   <font color=green>// Инициализация </font>
 
   <font color=green>// Инициализация </font>
   <tex> D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0] \rbrace </tex>
+
   <tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex>
   '''for''' <tex>i = 1</tex> '''to''' <tex>len(w)</tex>
+
   '''for''' <tex>i = 1</tex> '''to''' <tex>len(w) - 1</tex>
 
     <tex>D_i</tex> = <tex>\varnothing </tex>
 
     <tex>D_i</tex> = <tex>\varnothing </tex>
 
   <font color=green>// Вычисление ситуаций </font>
 
   <font color=green>// Вычисление ситуаций </font>
   '''for''' <tex>j = 0</tex> '''to''' <tex>len(w)</tex>
+
   '''for''' <tex>j = 0</tex> '''to''' <tex>len(w) - 1</tex>
 
     <tex>\mathtt{scan}(D, j, G, w)</tex>
 
     <tex>\mathtt{scan}(D, j, G, w)</tex>
 
     '''while''' <tex>D_j</tex> изменяется
 
     '''while''' <tex>D_j</tex> изменяется
Строка 45: Строка 45:
 
       <tex>\mathtt{predict}(D, j, G, w)</tex>
 
       <tex>\mathtt{predict}(D, j, G, w)</tex>
 
   <font color=green>// Результат </font>
 
   <font color=green>// Результат </font>
   '''if'''  <tex>[S' \rightarrow S \ \cdot, 0] \in D_{len(w)} </tex>
+
   '''if'''  <tex>[S' \rightarrow S \cdot, 0] \in D_{len(w)} </tex>
 
     '''return''' ''true''
 
     '''return''' ''true''
 
   '''else'''
 
   '''else'''
 
     '''return''' ''false''     
 
     '''return''' ''false''     
  
 
+
<font color=green>// Первое правило </font>
 
  '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>:
 
  '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>:
 
   '''if''' <tex>j</tex> == <tex>0</tex>
 
   '''if''' <tex>j</tex> == <tex>0</tex>
Строка 56: Строка 56:
 
   '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex>
 
   '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex>
 
     '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex>
 
     '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex>
       <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha a \cdot \beta, i]</tex>
+
       <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha \cdot a \beta, i]</tex>
 
+
 +
<font color=green>// Второе правило </font>
 
  '''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
 
  '''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
   '''for''' <tex>[B \rightarrow \eta \ \cdot, i] \in D_{j} </tex>
+
   '''for''' <tex>[B \rightarrow \eta \cdot, i] \in D_{j} </tex>
     '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, j] \in D_{i} </tex>
+
     '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i} </tex>
       <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, j]</tex>
+
       <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>
  
 +
<font color=green>// Третье правило </font>
 
  '''function''' <tex>\mathtt{predict}(D, j, G, w)</tex>:
 
  '''function''' <tex>\mathtt{predict}(D, j, G, w)</tex>:
 
   '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex>
 
   '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex>
 
     '''for''' <tex>(B \rightarrow \eta) \in P </tex>
 
     '''for''' <tex>(B \rightarrow \eta) \in P </tex>
       <tex>D_{j}</tex> <tex>\cup</tex>= <tex>[B \rightarrow \cdot \ \eta, j]</tex>
+
       <tex>D_{j}</tex> <tex>\cup</tex>= <tex>[B \rightarrow \cdot \eta, j]</tex>
  
 
==Корректность алгоритма==
 
==Корректность алгоритма==
 
{{Теорема
 
{{Теорема
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.  
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.  
То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta) \wedge A \Rightarrow^* w_i \ldots 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 =
  
Строка 78: Строка 80:
 
Докажем индукцией по исполнению алгоритма.<br/>
 
Докажем индукцией по исполнению алгоритма.<br/>
 
<u> ''База  индукции:'' </u><br/>
 
<u> ''База  индукции:'' </u><br/>
<tex>[S' \rightarrow \cdot S, 0] \in D_0 \ </tex>.<br/>
+
<tex>[S' \rightarrow \cdot S, 0] \in D_0</tex>.<br/>
 
<u> ''Индукционный переход:'' </u> <br/>
 
<u> ''Индукционный переход:'' </u> <br/>
 
Пусть предположение верно для всех списков ситуаций с номерами меньше <tex> j </tex>. Разберемся, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
 
Пусть предположение верно для всех списков ситуаций с номерами меньше <tex> j </tex>. Разберемся, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
  
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 \ldots w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i \ldots 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 \ldots w_{j-2}w_{j-1} = w_i \ldots 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 \ldots w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i \ldots 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 \ldots 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'} \ldots w_{i-1}</tex>.<br/>
+
и <tex> \alpha ' \Rightarrow^* w_{i'}...w_{i-1}</tex>.<br/>
Получаем, что <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0 \ldots w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \ldots 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 \ldots 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/>
 
По построению: <tex> \alpha = \alpha ' A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>.<br/>
 
По построению: <tex> \alpha = \alpha ' A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>.<br/>
Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
+
Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
  
 
<b><tex>\Longleftarrow</tex></b><br/>
 
<b><tex>\Longleftarrow</tex></b><br/>
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0 \ldots w_{i-1} A \delta \ </tex> из <tex>S'</tex> и  <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
+
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <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 \ldots w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
+
индукцию по длине вывода <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 \ldots 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 \ldots w_{i'-1} \wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}</tex>.<br/>
+
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 \ldots w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} w_i \ldots w_{i'-1}B \beta \delta</tex>,
+
Тогда имеем <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'} \ldots w_{j-1}</tex>.<br/>
+
а также <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>.
+
Применяя индукцию по второму параметру получим <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/>  
 
3. <tex>\alpha = \varepsilon </tex>, тогда <tex>i=j</tex>.<br/>  
 
Тогда либо <tex>i = 0 \wedge A = S \wedge \delta = \varepsilon</tex>, что доказывает базу индукции,<br/>
 
Тогда либо <tex>i = 0 \wedge A = S \wedge \delta = \varepsilon</tex>, что доказывает базу индукции,<br/>
либо вывод можно записать в виде <tex>S' \Rightarrow^* w_0 \ldots w{i'-1}w_{i'} \ldots w{i-1} A \delta ' \delta '' = w_0 \ldots w_{i-1} A \delta \ </tex> для некоторого правила <tex>(A' \rightarrow w_{i'} \ldots w_{i-1} A \delta ') \in P</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'} \ldots w_{i-1} A \delta ', i'] \in D_{i'} \ </tex>,  
+
Отсюда по предположению индукции <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'} \ldots w_{i-1} \cdot  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>, что и требовалось.
+
после чего по правилу <tex> \mathtt{predict}</tex> получим <tex>[A \rightarrow \cdot \beta, i] \in D_{j}</tex>, что и требовалось.
  
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: