• эадание множеств путем перечисления их элементов;
• выполнение операций над множествами (объединение,  пересечение, разность);
• вычисление  сложных скобочных выражений (с учетом приоритетов), составленных из операций над множествами;
• присваивание значения выражения множеству;
• печать элементов множества.

Реализовать переносимый  интерпретатор  языка  множеств, учитывая приведенные ниже требования.

2. Язык алгебры логики и его использование для решения задачи логической разрешимости.
Разработать язык алгебры логики [1], позволяющий:

• описывать сложные логические функции,  учитывая приоритет логических операций и используя скобочную форму записи;
• допустимыми логическими операциями являются И,  ИЛИ, НЕ и ИМПЛИКАЦИЯ;
• операндами логических операций могут быть константы,  переменные и ранее определенные функции.

Реализовать  программу, решающую задачу разрешимости логического выражения, т.е. программу, отыскивающую значения  переменных  логического  выражения (функции), доставляющие этому выражению истинное значение. Требования к программной реализации приведены ниже.

3. Лингвистический процессор для символьного дифференцирования.
Разработать язык, который должен позволять:

• описывать алгебраические выражения любой сложности, используя префиксную (функциональную) форму записи;
• описывать таблицы дифференцирования  для  используемых  в выражениях функций;
• печатать результат дифференцирования  ранее определенных функций;
• аргументами функций могут быть  константы,  переменные  и ранее определенные функции.

Разработать, учитывая приведенные ниже требования, программную реализацию лингвистического процессора.

4. Лингвистический процессор для численного интегрирования функций.
[Суханов РК6-73]
Разработать язык описания алгебраических выражений,  который должен обеспечивать:

• описание алгебраических выражений в стандартной математической нотации (учет  приоритетов  операций,  скобки,  инфиксные "+", "-", "*", "/", унарный "-" и т.п.);
• использование в выражениях функций  sin,  cos,  tg,  ctg, exp, ln, log и pow - целая степень;
• использование в выражениях констант и переменных;
• печать результата численного интегрирования.

Разработать, учитывая приведенные ниже требования,  лингвистический процессор, в которой должны быть реализованы 2 метода интегрирования.

5. [Собянин РК6-73] Транслятор nroff - html
Разработать транслятор документов в формате nroff в документы формата html.
Язык верстки текстовых документов nroff (и, соответственно, программа-верстатель nroff) широко используется в ОС UNIXдля представления документации на эту систему. Получить описание языка верстки nroff в любой версии ОС UNIX можно командой

man 5 man

more /usr[/share]/man/man5/man.5

Внимание. Данное задание обязательно должно быть реализовано средствами lex и yacc.
Примечание. Правильность работы транслятора будет проверяться сравнением облика результатов работы программы man и транслятора на реальных документах руководства ОС UNIX.

6. Верификатор описаний на языке VHDL
Разработать программу, осуществляющую проверку синтаксиса описаний на языке VHDL (Veryhighintegrated circiuts design language) цифровых устройств.
Неформальное описание языка VHDL дано в [2]. Описание языка VHDL также можно получить на дискете.
Примечание. Правильность работы верификатора будет проверяться путем сравнения с результатами работы реальной системы.

7. Транслятор VHDL - Пролог
Язык VHDL - язык описания цифровых систем (см. задание выше).
Язык Пролог (Prolog - programing in logic) имеет в качестве математической основы исчисление предикатов первого порядка и может быть использован, в частности, для вычисления значений логических выражений. Описание языка дано в [3, 4] и других источниках (например, http://rk6.bmstu.ru).
Необходимо разработать транслятор описаний комбинационных схем на языке VHDL в описания на языке Пролог. При разработке транслятора необходимо учесть следующие ограничения:

• цифровые схемы должны быть комбинационными, т.е. не должны иметь обратных связей;
• трансляции подлежит только структурная (топологическая) компонента исходного описания на языке VHDL;
• схемы должны состоять из элементов no (НЕ), andN (И, где количество входов N - от 2 до 5) и orN (И, где количество входов N - от 2 до 5);
• считается, что поведенческое описание на языке VHDL элементов no, andN и orN в системе проектирования VHDL хранится в стандартной библиотеке и транслятору недоступно;
• исходное описание на языке VHDL может носить иерархический характер и не должно содержать операторов поведенческого описания.

-------------- Объект проекта 2И-НЕ --------------

entity andno2 is   -- Описание интерфейса 2И-НЕ
  port (
    x1, x2: in Bit;
    y1: out Bit);
end andno2;

architecture StructAndNo2 of andno2 is   -- Описание
                        -- архитектурного тела 2И-НЕ
  component and2  -- список используемых компонентов
    port(a1, a2: in Bit; b1 out Bit);
  component no
    port(a: in Bit; b out Bit);

  begin                        -- описание топологии
    c1: and2
      port map(x1, x2, z1);
    c2: no
      port map(z1, y1);
end StructAndNo2;

--------------- Объект проекта Unit -----------------

entity unit is   -- Описание интерфейса Unit
  port (
    x1, x2, x3: in Bit;
    y1, y2: out Bit);
end unit;

architecture StructUnit of unit is        -- Описание
                          -- архитектурного тела Unit
  component andno2 -- список используемых компонентов
    port(a1, a2: in Bit; b1 out Bit);
  component and2
    port(a1, a2: in Bit; b1 out Bit);
  component or2
    port(a1, a2: in Bit; b1 out Bit);

  begin                        -- описание топологии
    c1: andno2
      port map(x1, x2, z1);
    c2: and2
      port map(x2, x3, z2);
    c3: andno2
      port map(z1, z2, y1);
    c4: or2
      port map(y1, z2, y2);

end StructUnit;

andno2(x1, x2, y1) :- and2(x1, x2, z1),
  no(z1, y1).

unit(x1, x2, x3, y1, y2) :- andno2(x1, x2, z1),
  and2(x2, x3, z2),
  and2(z1, z2, y1),
  and2(y1, z2, y2).

Примечание. Для демонстрации правильности работы программы необходимо подготовить небольшую БД, оформленную в виде базы фактов на языке Пролог.

Пример. Пусть есть две следующие таблицы реляционной БД.

SELECT s.name, s.id, m.discipline

  FROM students s, mlist m

  WHERE s.id = m.id AND s.name = 'Ivanov I.P.' AND m.mark > 3;

select(s_name, s_id, m_discipline) :-

  students(s_id, s_name, s_bdate), mlist(m_id, m_discipline, m_mark),

  s_id = m_id, s_name = 'Ivanov I.P.', m_mark > 3, fail.

Алгоритм преобразования состоит из следующих шагов [7].

1. Исключение из исходной формулы символов импликации, для чего используется ~F|G вместо F->G (где F и G - любые формулы ИППП, ~ - знак отрицания, | - символ дизъюнкции, & - символ коньюнкции).
2. Ограничение области действия отрицания только атомарными формулами, для чего используются правила деМоргана:
~F|~G вместо ~(F&G) ~F&~G вместо ~(F|G) При внесении отрицания в область действия квантора используются следующие правила: E^-1x~F вместо ~A^-1xF A^-1x~F вместо ~E^-1xF
3. Разделение переменных - переименование их с тем, чтобы каждый квантор имел свою переменную.
4. Исключение кванторов существования введением сколемовских констант и функций. Здесь формула вида

E^-1y(...P(y)...) заменяется формулой ...P(a)...
А формула вида
A^-1x(E^-1y(...P(x,y)...)) заменяется формулой Ax(...P(x,f(x))...)
где A обозначает квантор всеобщности, E - квантор существования, a - сколемовская константа, f(x) - сколемовская функция.
5. Вынесение кванторов всеобщности в начало формулы и их исключение из формулы.
6. Приведение формулы ("очищенной" от кванторов) в конъюктивную нормальную форму. Используется (F|G)&(F|H) вместо F|(G&H).
7. Исключение символа коньюнкции &, в результате образуется множество дизъюнктов, называемых также предложениями.

• оперирует только числовыми данными;
• не имеет операторов ввода-вывода (READ, PRINT, FORMAT);
• не имеет COMMON-блоков.

<идентификатор-типа><длина-содержимого><содержимое>

3026     SEQUENCE(38) = ...
  020100     INTEGER(1) = 0
  0405636973636F  OCT-STR(5) = "cisco"
  A01A     GetRequest-PDU(26) = ...
    02022219     INTEGER(2) = 8729
    020100     INTEGER(1) = 0
    020100     INTEGER(1) = 0
    300E     SEQUENCE(14) = ...
      300C     SEQUENCE(12) = ...
        06082D06010201020100  OBJ-ID(8) = 1.3.6.1.2.1.2.1.0
        0500     NULL