317
правок
Изменения
→Время работы для однозначной грамматики
Следовательно, <tex>\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j</tex> и <tex>\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j</tex>.<br/>
Заметим, что <tex>S \Rightarrow^* \gamma A \delta \Rightarrow^* a_1 \ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta</tex>. Предположим, что <tex>\beta \delta \Rightarrow^* w'</tex> (ведь в грамматике нет непорождающих нетерминалов). Тогда <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_1 w'</tex> и аналогично <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_2 w'</tex>.<br/>
Таким образом, если <tex>k_1 \ne k_2</tex>, то подстрока <tex>a_{i+1} \ldots a_j</tex> выводится двумя различными способами из <tex>\alpha' \eta_1</tex> и <tex>\alpha' \eta_2</tex> (поскольку в первом случае <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex>, а во втором <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>), то есть у строки <tex>a_1 \ldots a_jw'</tex> есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>k_1 = k_2</tex>, то <tex>\eta_1 \ne \eta_2</tex>, что приводит к аналогичному противоречию. Суммируя выше сказанное, отметим, что противоречие получается из того факта, что в некоторый момент времени (то есть для подстроки <tex>a_1 \dots a_i</tex>) мы получаем два различных дерева вывода. Поэтому, в дальнейшем, при выводе суффикса <tex>a_{i+1} \dots a_n</tex>, каким образом мы его не получим, деревьев вывода будет как минимум два, поскольку они будут получаться заменой какого-то листа (терминального символа) на какое-то правило (поддерево из нетерминалов и терминалов),таким образом, получаем противоречие с однозначностью (по определению [[Существенно_неоднозначные_языки | неоднозачной грамматики]])
}}
