Алгоритм Эрли - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:27:11Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:48, 1 сентября 2022

2022-09-01T04:48:12Z

Gaporf: Исправил многоточия ещё

2019-05-23T19:35:28Z

Исправил многоточия ещё

Gaporf: Исправил многоточия

2019-05-23T17:50:23Z

Исправил многоточия

Gaporf: /* Псевдокод */ Исправил псевдокод

2019-05-14T20:27:00Z

‎Псевдокод: Исправил псевдокод

Gaporf: /* Корректность алгоритма */

2019-05-14T20:20:15Z

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

Gaporf в 19:05, 14 мая 2019

2019-05-14T19:05:10Z

Gaporf: /* Алгоритм Эрли */

2019-05-14T18:53:32Z

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

Shovkoplyas Grigory в 17:34, 18 января 2016

2016-01-18T17:34:41Z

Shovkoplyas Grigory в 17:26, 18 января 2016

2016-01-18T17:26:12Z

← Предыдущая		Версия 16:27, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	__TOC__		__TOC__
	'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.		'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.

← Предыдущая		Версия 04:48, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	__TOC__		__TOC__
	'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.		'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.

@@ Строка 19: / Строка 19: @@
 {{Определение
 |definition =
-Последовательность списков ситуаций <tex>D_0, D_1, .., D_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
+Последовательность списков ситуаций <tex>D_0, D_1, \ldots, D_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
 }}

@@ Строка 7: / Строка 7: @@
 {{Определение
 |definition =
-Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 ... w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
+Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 \ldots 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>).
 }}
@@ Строка 13: / Строка 13: @@
 {{Определение
 |definition =
-Ситуации хранятся в множествах <tex>D_0,...,D_{n-1}</tex>, называемых '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что
+Ситуации хранятся в множествах <tex>D_0, \ldots ,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...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</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>.
 }}
@@ Строка 71: / Строка 71: @@
 {{Теорема
 |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 \ldots w_{i-1} A \delta) \wedge A \Rightarrow^* w_i \ldots w_{j-1})</tex>
 |proof =
@@ Строка 84: / Строка 84: @@
 . Включаем по правилу <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>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 \ldots w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i \ldots 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 \ldots w_{j-2}w_{j-1} = w_i \ldots 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 \ldots w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i \ldots w_{j-1}</tex> выполняются.
 . Включаем по правилу <tex> \mathtt{predict} \ </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 \ldots w_{i'-1} A' \delta ''</tex>
-и <tex> \alpha ' \Rightarrow^* w_{i'}...w_{i-1}</tex>.<br/>
+и <tex> \alpha ' \Rightarrow^* w_{i'} \ldots 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 \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>, в итоге <tex> S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, что нам и требовалось.
+</tex>, в итоге <tex> S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, что нам и требовалось.
 . Включаем по правилу <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/>
-Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
+Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
 <b><tex>\Longleftarrow</tex></b><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_0 \ldots w_{i-1} A \delta \ </tex> из <tex>S'</tex> и  <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
-индукцию по длине вывода <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
+индукцию по длине вывода <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
 Рассмотрим три случая последнего символа <tex>\alpha</tex>:
-. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i...w_{j-2}</tex>.<br/>
+. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i \ldots 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>\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>\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/>
-Тогда имеем <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>[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>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}</tex>.<br/>
+а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'} \ldots 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>\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>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>[A' \rightarrow \cdot w_{i'}...w_{i-1} A \delta ', i'] \in D_{i'} \ </tex>,
+Отсюда по предположению индукции <tex>[A' \rightarrow \cdot w_{i'} \ldots 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{scan}</tex> приводит к <tex>[A' \rightarrow w_{i'} \ldots 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>, что и требовалось.

@@ Строка 36: / Строка 36: @@
     <font color=green>// Инициализация </font>
     <tex> D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0] \rbrace </tex>
-    '''for''' <tex>i = 1</tex> '''to''' <tex>len(w) - 1</tex>
+    '''for''' <tex>i = 1</tex> '''to''' <tex>len(w)</tex>
       <tex>D_i</tex> = <tex>\varnothing </tex>
     <font color=green>// Вычисление ситуаций </font>
-    '''for''' <tex>j = 0</tex> '''to''' <tex>len(w) - 1</tex>
+    '''for''' <tex>j = 0</tex> '''to''' <tex>len(w)</tex>
       <tex>\mathtt{scan}(D, j, G, w)</tex>
       '''while''' <tex>D_j</tex> изменяется
@@ Строка 50: / Строка 50: @@
       '''return''' ''false''
- <font color=green>// Первое правило </font>
   '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>:
     '''if''' <tex>j</tex> == <tex>0</tex>
@@ Строка 56: / Строка 56: @@
     '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex>
       '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex>
-        <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha \cdot a \beta, i]</tex>
+        <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha a \cdot \beta, i]</tex>
-−
   '''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
     '''for''' <tex>[B \rightarrow \eta \ \cdot, i] \in D_{j} </tex>
-      '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i} </tex>
+      '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, j] \in D_{i} </tex>
-        <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>
+        <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, j]</tex>
   '''function''' <tex>\mathtt{predict}(D, j, G, w)</tex>:
     '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </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>[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>:
     <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) - 1</tex>
       <tex>D_i</tex> = <tex>\varnothing </tex>
@@ Строка 45: / Строка 45: @@
         <tex>\mathtt{predict}(D, j, G, w)</tex>
     <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''
     '''else'''
@@ Строка 60: / Строка 60: @@
   <font color=green>// Второе правило </font>
   '''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, k] \in D_{i} </tex>
         <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>
@@ Строка 68: / Строка 68: @@
     '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </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>
 ==Корректность алгоритма==

← Предыдущая		Версия 17:34, 18 января 2016
Строка 1:		Строка 1:
−	~~==Определения==~~	+	__TOC__
	'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.		'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободной]] грамматике <tex>G</tex>.

@@ Строка 1: / Строка 1: @@
 '''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
@@ Строка 4: / Строка 5: @@
 '''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
 {{Определение
 |definition =