Теория вычислительных процессов и структур. Селиверстов М.Н. - 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. Трансляции, их представление и реализация: трансляции и трансляторы; схемы
синтаксически-управляемой трансляции; магазинные преобразователи и синтаксически-

                                          4