Викиконспекты - Вклад участника [ru]

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

2017-01-04T19:11:28Z

37.113.172.118:

==Алгоритм==
Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]].

Будем рассматривать грамматику [[Удаление eps-правил из грамматики|без ε-правил]] и [[Удаление бесполезных символов из грамматики|бесполезных символов]].

<tex>I_0</tex> = <tex>\{[S' \rightarrow \cdot S, 0]\}</tex> # Правило (0) — инициализация
useful_loop(0)

for j = 1..n
for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>
<tex>I_j</tex> ∪= <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> # Правило (1)
useful_loop(j)

function useful_loop(j):
<tex>I_j'' = I_j</tex>
while <tex>I_j'' \ne \varnothing</tex>
<tex>I_j' = I_j''</tex>
<tex>I_j'' = \varnothing</tex>
for <tex>[B \rightarrow \eta \cdot , i] \in I_j'</tex> # (*)
for <tex>[A \rightarrow \alpha \cdot B \beta, k] \in I_{i}</tex>
<tex>I_j''</tex> ∪= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex> # Правило (2)

for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j'</tex> # (**)
for <tex>\beta : (A \rightarrow \beta) \in P</tex>
<tex>I_j''</tex> ∪= <tex>[A \rightarrow \cdot \beta, j]</tex> # Правило (3)
<tex>I_j</tex> ∪= <tex>I_j''</tex>

В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex>, просматривается не весь список <tex>I_j</tex>, а только те ситуации, которые были добавлены на предыдущей итерации цикла <code>while</code>. Данная модификация является корректной.
# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S', \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S'</tex> не встречается в правых частях правил.
# Теперь рассмотрим цикл <tex>(**)</tex>. Так как для каждой ситуации <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex> в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex>.
Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах <tex>(*)</tex> и <tex>(**)</tex> просматривается подмножество полного списка. Значит этот алгоритм эквивалентен оригинальному.

==Время работы для однозначной грамматики==
{{Лемма
|about=1
|statement=
<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше некоторой константы. Таким образом, поскольку в <tex>I_j</tex> находятся ситуации, у которых <tex>0 \le i \le j</tex>, всего в <tex>I_j</tex> будет <tex>O(j)</tex> ситуаций.
}}

{{Лемма
|about=2
|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>.
|proof=
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две ситуации <tex>[B \rightarrow \eta_1 \cdot, k_1]</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_2]</tex> (они различны, так как в цикле <tex>(*)</tex> каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_{k_1}</tex> и в <tex>I_{k_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>\eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>.
Следовательно, <tex>\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j</tex> и <tex>\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j</tex>. 
Заметим, что <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>. 
Таким образом, если <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>, что приводит к аналогичному противоречию.
}}

{{Теорема
|statement=
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
|proof=
Орагнизуем каждый список разбора <tex>I_j</tex> таким образом, чтобы по любому символу <tex>x \in \Sigma \cup N</tex>, можно было за <tex>O(1)</tex> получить список тех и только тех ситуаций, содержащихся в <tex>I_j</tex>, которые имеют вид <tex>[A \rightarrow \alpha \cdot x \beta, j]</tex>.

Время построения <tex>I_0</tex> не зависит от входной строки.

Рассмотрим <tex>I_j, \, j > 0</tex>.
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
# Рассмотрим правило <tex>(2)</tex>. Можно считать, что внутри цикла <tex>(*)</tex> рассматриваются те и только те ситуации, которые удовлетворяют условию (так как список таких ситуаций можно по нетерминалу получить за <tex>O(1)</tex>). Тогда каждая такая ситуация будет добавлена в список и, исходя из леммы 2, попытка добавления будет единственной. А так как по лемме 1 всего в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций, то суммарно за все итерации внешнего цикла while внутри цикла <tex>(*)</tex> будет рассмотрено <tex>O(j)</tex> ситуаций.
# Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено <tex>O(1)</tex> операций.
Таким образом, на построение списка <tex>I_j</tex> будет потрачено <tex>O(j)</tex> операций. Тогда время работы алгоритма составляет <tex>O(n^2)</tex>.
}}

== См. также ==
* [[Алгоритм_Эрли | Алгоритм Эрли]]
* [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ | Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ ]]

== Источники информации==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Теорема Клини (совпадение классов автоматных и регулярных языков)

2017-01-03T16:55:04Z

37.113.172.118: /* Источники информации */

{{Теорема
|author=Клини
|statement=Классы [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков совпадают.
|proof=
[[Файл:Reg0.png|200px|thumb|right|Автоматы для регулярных языков нулевого поколения]]
[[Файл:cup.png|200px|thumb|right|Автомат для объединения двух регулярных языков]]
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]

*<tex>\mathrm{REG} \subseteq \mathrm{AUT}</tex>.

Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка.

'''База'''
:<tex>n = 0</tex>.
:Для этого достаточно построить автоматы для трех языков:
:#<tex>L = \varnothing</tex>,
:#<tex>L = \left\{\varepsilon \right\}</tex>,
:#<tex>L = \left\{c \right\}</tex>.

'''Индукционный переход'''
:Умеем строить автоматы для языков <tex>n</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.
:Для этого достаточно научиться строить автоматы для следующих языков (<tex>L, M \in \mathrm{R_n}</tex>):
:#<tex>L^\prime = L \cup M</tex>,
:#<tex>L^\prime = LM</tex>,
:#<tex>L^\prime = L^*</tex>.
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.

'''Итого''', мы можем по регулярному выражению построить автомат, допускающий тот же язык.

 
*<tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex>.

Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.

Определим регулярные выражения, задающие следующие множества слов:

:<tex>\xi_{ijk} = \left\{ s \mid \langle i,s \rangle \vdash^* \langle j, \varepsilon \rangle \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.
 
Построим эти регулярные выражения:
#<tex>\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в него же самого.
#<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в состояние <tex>j</tex>.
#<tex>\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*</tex>.
#<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex>.
 
Теперь нетрудно задать регулярное выражение для всего языка:

:<tex>\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_2}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> — стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> — терминальные состояния исходного автомата.

'''Таким образом''', мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}

== См. также ==
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Детерминированные конечные автоматы]]

== Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 Википедия {{---}} Теорема Клини]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Теорема Клини (совпадение классов автоматных и регулярных языков)

2017-01-03T16:54:48Z

37.113.172.118: /* Источники информации */

{{Теорема
|author=Клини
|statement=Классы [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков совпадают.
|proof=
[[Файл:Reg0.png|200px|thumb|right|Автоматы для регулярных языков нулевого поколения]]
[[Файл:cup.png|200px|thumb|right|Автомат для объединения двух регулярных языков]]
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]

*<tex>\mathrm{REG} \subseteq \mathrm{AUT}</tex>.

Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка.

'''База'''
:<tex>n = 0</tex>.
:Для этого достаточно построить автоматы для трех языков:
:#<tex>L = \varnothing</tex>,
:#<tex>L = \left\{\varepsilon \right\}</tex>,
:#<tex>L = \left\{c \right\}</tex>.

'''Индукционный переход'''
:Умеем строить автоматы для языков <tex>n</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.
:Для этого достаточно научиться строить автоматы для следующих языков (<tex>L, M \in \mathrm{R_n}</tex>):
:#<tex>L^\prime = L \cup M</tex>,
:#<tex>L^\prime = LM</tex>,
:#<tex>L^\prime = L^*</tex>.
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.

'''Итого''', мы можем по регулярному выражению построить автомат, допускающий тот же язык.

 
*<tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex>.

Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.

Определим регулярные выражения, задающие следующие множества слов:

:<tex>\xi_{ijk} = \left\{ s \mid \langle i,s \rangle \vdash^* \langle j, \varepsilon \rangle \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.
 
Построим эти регулярные выражения:
#<tex>\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в него же самого.
#<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в состояние <tex>j</tex>.
#<tex>\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*</tex>.
#<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex>.
 
Теперь нетрудно задать регулярное выражение для всего языка:

:<tex>\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_2}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> — стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> — терминальные состояния исходного автомата.

'''Таким образом''', мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}

== См. также ==
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Детерминированные конечные автоматы]]

== Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 Википедия {{---}} Теорема Клини]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
* [https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/regular-exp.pdf Regular Expressions {{---}} Deepak D’Souza]

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]