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

Регулярная аппроксимация КС-языков

2014-01-19T01:22:14Z

46.19.184.86: добавил алгоритм преобразования

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''', если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}
== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике.

}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Ввведем функцию <tex> recursive(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>

'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>

'''function''' recursive (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRihtType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRihtType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRihtType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRihtType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>recursive(N_i) \neq self </tex>, т.к грамматика не самоприменима.
В основе алгоритма будет рекурсивный обход грамматики во все стороны. Спускаемся по грамматике до тех пор не приходим в терминал или символ алфавита:
# символ алфавит или <tex> /varepsilon </tex> {{---}} добовляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный терминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</tex> {{---}} множество переходов ДКА.
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)

'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> <font color=green>// пришли в лист дерева разбора</font>
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if recursive'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' <font color=green>// рекурсивный нетерминал rihgt или self</font>
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)

Регулярная аппроксимация КС-языков

2014-01-18T21:52:15Z

46.19.184.86: start

Теория формальных языков

2014-01-18T21:11:32Z

46.19.184.86: /* Контекстно-свободные грамматики */

[[Категория: Теория формальных языков]]
== Автоматы и регулярные языки ==
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
*[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]
*[[Детерминированные конечные автоматы]]
*[[Прямое произведение ДКА]]
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
*[[Замкнутость регулярных языков относительно различных операций]]
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Решение уравнений в регулярных выражениях]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Контексты и синтаксические моноиды]]

== Контекстно-свободные грамматики ==
*[[Формальные грамматики]]
*[[Иерархия Хомского формальных грамматик]]
*[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
*[[Правоконтекстные грамматики, эквивалентность автоматам]]
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
*[[Замкнутость КС-языков относительно различных операций]]
*[[Регулярная аппроксимация КС-языков]]
=== Нормальные формы КС-грамматик ===
*[[Удаление бесполезных символов из грамматики]]
*[[Удаление eps-правил из грамматики]]
*[[Удаление цепных правил из грамматики]]
*[[Удаление длинных правил из грамматики]]
*[[Нормальная форма Хомского]]
*[[Устранение левой рекурсии]]
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
=== Алгоритмы разбора ===
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
*[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
*[[Алгоритм Эрли]]
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
=== Опровержение контекстно-свободности языка ===
*[[Лемма о разрастании для КС-грамматик]]
*[[Лемма Огдена]]
*[[Существенно неоднозначные языки]]
=== МП-автоматы ===
*[[Автоматы с магазинной памятью]]
*[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
*[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
*[[Детерминированные автоматы с магазинной памятью]]
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
*[[Нормальная форма ДМП-автомата]]
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]

== Теория вычислимости ==
=== Разрешимые и перечислимые языки ===
*[[Разрешимые (рекурсивные) языки]]
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Вычислимые функции]]
*[[Вычислимые числа]]
*[[Диагональный метод]]
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
*[[Главные нумерации]]
*[[Неотделимые множества]]
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
*[[Busy beaver]]

=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]
*[[Примитивно рекурсивные функции]]
*[[Частично рекурсивные функции]]
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]

=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
*[[Неразрешимость исчисления предикатов первого порядка]]
*[[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]

*[[Теорема Райса-Шапиро]]