Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Лемма |statement= Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} однозначная КС-грамматика и <tex>a_1 \dots a_n</tex> {{---}} ц...»)
 
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} однозначная КС-грамматика и <tex>a_1 \dots a_n</tex> {{---}} цепочка из <tex>\Sigma^*</tex>. Тогда алгоритм Эрли пытается включить <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> в <tex>I_j</tex> не более одного раза, если <tex>\alpha \ne \varepsilon</tex>
+
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} однозначная КС-грамматика и <tex>a_1 \dots a_n</tex> {{---}} цепочка из <tex>\Sigma^*</tex>. Тогда алгоритм Эрли пытается включить <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> в <tex>I_j</tex> не более одного раза, если <tex>\alpha \ne \varepsilon</tex>.
 
|proof=
 
|proof=
 
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только на шагах <tex>(2)</tex>, <tex>(4)</tex>, или <tex>(5)</tex>. Если она включается на шаге <tex>(4)</tex>, то последний символ цепочки <tex>\alpha</tex> {{---}} терминал, а если на шагах <tex>(2)</tex> или <tex>(5)</tex>, то {{---}} нетерминал. В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \gamma \cdot, k]</tex> и <tex>[B \rightarrow \delta \cdot, l]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_k</tex> и в <tex>I_l</tex>.
 
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только на шагах <tex>(2)</tex>, <tex>(4)</tex>, или <tex>(5)</tex>. Если она включается на шаге <tex>(4)</tex>, то последний символ цепочки <tex>\alpha</tex> {{---}} терминал, а если на шагах <tex>(2)</tex> или <tex>(5)</tex>, то {{---}} нетерминал. В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \gamma \cdot, k]</tex> и <tex>[B \rightarrow \delta \cdot, l]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_k</tex> и в <tex>I_l</tex>.
 
#Пусть <tex>k \ne l</tex>. Тогда по теореме существуют такие <tex>\theta_1, \theta_2, \theta_3</tex> и <tex>\theta_4</tex>, что <tex>S \Rightarrow^* \theta_1 A \theta_2 \Rightarrow \theta_1 \alpha' B \beta \theta_2 \Rightarrow^* a_1 \dots a_n</tex> и <tex>S \Rightarrow^* \theta_3 A \theta_4 \Rightarrow \theta_3 \alpha' B \beta \theta_4 \Rightarrow^* a_1 \dots a_n</tex>. Но в первом выводе <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_k</tex>, а во втором <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_l</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
 
#Пусть <tex>k \ne l</tex>. Тогда по теореме существуют такие <tex>\theta_1, \theta_2, \theta_3</tex> и <tex>\theta_4</tex>, что <tex>S \Rightarrow^* \theta_1 A \theta_2 \Rightarrow \theta_1 \alpha' B \beta \theta_2 \Rightarrow^* a_1 \dots a_n</tex> и <tex>S \Rightarrow^* \theta_3 A \theta_4 \Rightarrow \theta_3 \alpha' B \beta \theta_4 \Rightarrow^* a_1 \dots a_n</tex>. Но в первом выводе <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_k</tex>, а во втором <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_l</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
 
#Пусть <tex>k = l</tex>. Тогда <tex>\gamma \ne \delta</tex>.  Тогда, так как <tex>[B \rightarrow \gamma \cdot, k] \in I_j</tex> и <tex>[B \rightarrow \delta \cdot, k] \in I_j</tex>, то <tex>\gamma \Rightarrow a_{k+1} \dots a_j</tex> и <tex>\delta \Rightarrow a_{k+1} \dots a_j</tex>, то есть <tex>a_{k+1} \dots a_j</tex> выводится двумя разными способами.
 
#Пусть <tex>k = l</tex>. Тогда <tex>\gamma \ne \delta</tex>.  Тогда, так как <tex>[B \rightarrow \gamma \cdot, k] \in I_j</tex> и <tex>[B \rightarrow \delta \cdot, k] \in I_j</tex>, то <tex>\gamma \Rightarrow a_{k+1} \dots a_j</tex> и <tex>\delta \Rightarrow a_{k+1} \dots a_j</tex>, то есть <tex>a_{k+1} \dots a_j</tex> выводится двумя разными способами.
 +
}}
 +
 +
{{Теорема
 +
|statement=
 +
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
 +
|proof=
 
}}
 
}}

Версия 05:48, 3 ноября 2011

Лемма:
Пусть [math]G = (N, \Sigma, P, S)[/math] — однозначная КС-грамматика и [math]a_1 \dots a_n[/math] — цепочка из [math]\Sigma^*[/math]. Тогда алгоритм Эрли пытается включить [math][A \rightarrow \alpha \cdot \beta, i][/math] в [math]I_j[/math] не более одного раза, если [math]\alpha \ne \varepsilon[/math].
Доказательство:
[math]\triangleright[/math]

Ситуацию [math][A \rightarrow \alpha \cdot \beta, i][/math] можно включить в [math]I_j[/math] только на шагах [math](2)[/math], [math](4)[/math], или [math](5)[/math]. Если она включается на шаге [math](4)[/math], то последний символ цепочки [math]\alpha[/math] — терминал, а если на шагах [math](2)[/math] или [math](5)[/math], то — нетерминал. В первом случае результат очевиден. Во втором случае допустим, что [math][A \rightarrow \alpha'B \cdot \beta, i][/math] включается в [math]I_j[/math], когда рассматриваются две различные ситуации [math][B \rightarrow \gamma \cdot, k][/math] и [math][B \rightarrow \delta \cdot, l][/math]. Тогда ситуация [math][A \rightarrow \alpha' \cdot B\beta, i][/math] должна оказаться одновременно в [math]I_k[/math] и в [math]I_l[/math].

  1. Пусть [math]k \ne l[/math]. Тогда по теореме существуют такие [math]\theta_1, \theta_2, \theta_3[/math] и [math]\theta_4[/math], что [math]S \Rightarrow^* \theta_1 A \theta_2 \Rightarrow \theta_1 \alpha' B \beta \theta_2 \Rightarrow^* a_1 \dots a_n[/math] и [math]S \Rightarrow^* \theta_3 A \theta_4 \Rightarrow \theta_3 \alpha' B \beta \theta_4 \Rightarrow^* a_1 \dots a_n[/math]. Но в первом выводе [math]\theta_1 \alpha' \Rightarrow^* a_1 \dots a_k[/math], а во втором [math]\theta_1 \alpha' \Rightarrow^* a_1 \dots a_l[/math]. Тогда для цепочки [math]a_1 \dots a_n[/math] существуют два разных дерева вывода, в которых [math]a_{i+1} \dots a_j[/math] выводится из [math]\alpha' B[/math] двумя разными способами.
  2. Пусть [math]k = l[/math]. Тогда [math]\gamma \ne \delta[/math]. Тогда, так как [math][B \rightarrow \gamma \cdot, k] \in I_j[/math] и [math][B \rightarrow \delta \cdot, k] \in I_j[/math], то [math]\gamma \Rightarrow a_{k+1} \dots a_j[/math] и [math]\delta \Rightarrow a_{k+1} \dots a_j[/math], то есть [math]a_{k+1} \dots a_j[/math] выводится двумя разными способами.
[math]\triangleleft[/math]
Теорема:
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины [math]n[/math] составляет [math]O(n^2)[/math].