Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7
СодержаниеГ.М.Сергиевский, М.А.Короткова, 2004
1. Алфавит, слова, операции над словами
XYYX. Для конкатенации, как и для произведения, конкатенация n
Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.
2. Языки. Операции над языками
2.1. Теоретико-множественные операции
2.2.Специфические операции
V* (алфавит можно рассматривать как язык, состоящий из односимвольных слов) образует язык, состоящий из всех возможных цепочек,
3. Абстрактные формальные системы
Каноническая система
А существует каноническая система над А
4. Формальные порождающие грамматики
5. Классификация грамматик
6. А-языки. Конечные лингвистические автоматы 6.1. Диаграмма грамматики
6.2. Порождение и распознавание цепочек
F автомата как отображение Q V
6.3. Детерминизация недетерминированных автоматов
A, то найдется конечный автомат A'
6.4. Автоматы с -переходами
Детерминизация автоматов с -переходами
Оптимизация автоматов с -переходами
6.5. Минимизация числа состояний автомата
Минимизация автоматов по методу Хафмена
Минимизация не полностью определенных автоматов
6.6. Регулярные множества и регулярные выражения
0 – регулярное выражение, обозначающее регулярное множество
P, Q – регулярные множества, которым сопоставлены А
6.7. Разрешимые проблемы для А-грамматик
7. Нотации для задания КС-грамматик 7.1. Математическая нотация
7.2. Бекусова нормальная форма
7.3. Расширенная форма Бекуса – Наура (РБНФ)
Идентификатор = буква буква цифра.
7.4. Синтаксическая диаграмма
8. Структура цепочек. СУ-схемы
G. Пусть дана грамматика G
L называется неоднозначным, если для него не существует однозначной грамматики. Например, L={a
9. Преобразования КС-грамматик
9.1 Устранение непроизводящих правил
А имеют следующий вид и других правил для А
Алгоритм устранения непроизводящих нетерминалов.
9.2. Устранение недостижимых нетерминалов
Алгоритм преобразования грамматики.
9.3. Устранение -правил
Алгоритм преобразования грамматики.
9.4. Устранение цепных правил (правил вида А В)
Алгоритм исключения цепных правил.
10. Разрешимые и неразрешимые свойства КС-грамматик 10.1. Разрешимые свойства КС-грамматик
10.2. Неразрешимые свойства КС-грамматик
11. Синтаксический анализ для КС-языков
11.1. Типовая задача синтаксического анализа
LL(k)-грамматиками называются грамматики, допускающие детерминированное построение левого разбора (left)
LL(1)-грамматик. Грамматики могут оказаться LL(k)
S abAabB
Теорема 20. LL(k)
Использование LL(k) свойства при построении анализатора.
LL(1)-грамматика. Тогда существуют два вывода: S
11.3. Восходящий анализ
LR(k)-грамматик – тот тип грамматик, для которых однозначно восстанавливается правый вывод (R)
S, либо дальнейшие свертки окажутся невозможными. Отношения простого предшествования с указанными свойствами могут быть определе
Алгоритм разбора для ГПП.
12.Элементы теории конечных автоматов 12.1. Автомат Мили
Q соответствует вершина; множество ребер определяется отображениями F
Метод Хафмена минимизации числа состояний автомата
Алгоритм минимизации автомата
12.2. Автоматы Мура
12.3. Частичные автоматы
13. Сети автоматов. Их анализ и синтез
13.1. Синхронные сети автоматов
А (рис. 36,б). В получаемом автомате S =
13.2. Правильно построенные логические сети
