ВУЗ:
Составители:
Рубрика:
4
Реферат - -
Другие виды самостоятельной работы - -
Вид итогового контроля (зачет, экзамен) 9 зачет
экзамен
4. Содержание дисциплины.
4.1. Разделы дисциплины и виды занятий
Объем в часах №
п/п
Раздел дисциплины
Лекции Лаб.раб.
1 Теория формальных языков. 2 6
2 Теория синтаксического анализа и трансляций. 2 4
3 Трансляторы и методы их разработки. 8 12
4 Теория схем программ. 4
5 Оптимизация программ. 4 8
6 Семантическая теория программ. 2
7 Модели вычислительных процессов. 4 2
8 Сети Петри. 6 2
4.2. Содержание разделов дисциплины
Теория формальных языков
1. Языки и их представление: алфавиты и языки, представление языков.
2. Грамматики: мотивировка; формальное определение грамматики; язык, порож-
даемый грамматикой; классификация грамматик по Н.Хомскому; рекурсивность контек-
стно-зависимых грамматик; деревья вывода в контекстно-свободных грамматиках.
3. Конечные автоматы и регулярные грамматики: детерминированные и недетер-
минированные конечные автоматы и регулярные множества; эквивалентность конечных
автоматов и грамматик типа 3; свойства языков типа 3; регулярные выражения, построе-
ние конечного автомата по регулярному выражению; минимизация числа состояний ко-
нечного автомата; алгоритмически разрешимые проблемы, касающиеся конечных автома-
тов.
4. Контекстно-свободные грамматики и магазинные автоматы: упрощение кон-
текстно-свободных грамматик; нормальная форма Хомского; нормальная форма Грейбаха;
разрешимость конечности КС-языков; ε-правила в контекстно-свободных грамматиках;
специальные типы контекстно-свободных языков и грамматик. Нетерминированные и де-
терминированные магазинные автоматы; эквивалентность недерминированных магазин-
ных автоматов и КС-грамматик.
5. Машины Тьюринга: проблема остановки, языки типа 0; универсальная машина
Тьюринга; неразрешимость проблемы остановки; класс рекурсивных множеств; машины
Тьюринга и грамматики типа 0.
6. Линейно ограниченные автоматы и контекстно-зависимые языки: эквивалент-
ность линейно ограниченных автоматов и контекстно-зависимых грамматик; контекстно-
зависимые языки – подкласс рекурсивных множеств.
Теория синтаксического анализа и трансляций
7. Трансляции, их представление и реализация: трансляции и трансляторы; схемы
синтаксически-управляемой трансляции; магазинные преобразователи и синтаксически-
Реферат - - Другие виды самостоятельной работы - - Вид итогового контроля (зачет, экзамен) 9 зачет экзамен 4. Содержание дисциплины. 4.1. Разделы дисциплины и виды занятий № Объем в часах Раздел дисциплины п/п Лекции Лаб.раб. 1 Теория формальных языков. 2 6 2 Теория синтаксического анализа и трансляций. 2 4 3 Трансляторы и методы их разработки. 8 12 4 Теория схем программ. 4 5 Оптимизация программ. 4 8 6 Семантическая теория программ. 2 7 Модели вычислительных процессов. 4 2 8 Сети Петри. 6 2 4.2. Содержание разделов дисциплины Теория формальных языков 1. Языки и их представление: алфавиты и языки, представление языков. 2. Грамматики: мотивировка; формальное определение грамматики; язык, порож- даемый грамматикой; классификация грамматик по Н.Хомскому; рекурсивность контек- стно-зависимых грамматик; деревья вывода в контекстно-свободных грамматиках. 3. Конечные автоматы и регулярные грамматики: детерминированные и недетер- минированные конечные автоматы и регулярные множества; эквивалентность конечных автоматов и грамматик типа 3; свойства языков типа 3; регулярные выражения, построе- ние конечного автомата по регулярному выражению; минимизация числа состояний ко- нечного автомата; алгоритмически разрешимые проблемы, касающиеся конечных автома- тов. 4. Контекстно-свободные грамматики и магазинные автоматы: упрощение кон- текстно-свободных грамматик; нормальная форма Хомского; нормальная форма Грейбаха; разрешимость конечности КС-языков; ε-правила в контекстно-свободных грамматиках; специальные типы контекстно-свободных языков и грамматик. Нетерминированные и де- терминированные магазинные автоматы; эквивалентность недерминированных магазин- ных автоматов и КС-грамматик. 5. Машины Тьюринга: проблема остановки, языки типа 0; универсальная машина Тьюринга; неразрешимость проблемы остановки; класс рекурсивных множеств; машины Тьюринга и грамматики типа 0. 6. Линейно ограниченные автоматы и контекстно-зависимые языки: эквивалент- ность линейно ограниченных автоматов и контекстно-зависимых грамматик; контекстно- зависимые языки – подкласс рекурсивных множеств. Теория синтаксического анализа и трансляций 7. Трансляции, их представление и реализация: трансляции и трансляторы; схемы синтаксически-управляемой трансляции; магазинные преобразователи и синтаксически- 4
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »