Ответы_экзамен_2009 (1115077), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

A  .

Следовательно, L(G₂){ }. Таким образом, L(G₁)L(G₂), т.к.   L(G₂),   L(G₁).

КРИТЕРИИ: (а) нет ответа; определение с ошибками: –5

(б) нет ответа; неверный ответ; нет обоснования; неверное обоснование: –5

Замечание. Для обоснования неэквивалентности достаточно привести одну различающую цепочку.

Ответ почти эквивалентны считать верным.

Ответ: (a) G: S  c | Sc | Ac

A  Bb| Aa

B  Aa | Bb | b

(б) Разбор недетерминирован, т.к. автомат A не является детерминированным: из состояния A возможен переход в более чем одно состояние (по символу а). [или: т.к. из состояния B возможен переход в более чем одно состояние (по символу b)]

(в)

Построим таблицу переходов для A_D :

Начальное состояние: { H }. Заключительное состояние: { S }.

A_D :

Допускаются другие способы построения, дающие в итоге такой же автомат A_D с точностью до обозначений вершин.

КРИТЕРИИ: (а) нет ответа; грамматика построена, но неэквивалентная или не соответствующая
диаграмме : –3

(б) нет ответа; неверный ответ; ошибочное объяснение : –3

(в) нет ответа или программа на C++ приведена;

неэквивалентный или недетерм. автомат построен : –4

Ответ: Описание буквы «N» размера nn — это цепочка cⁿf ⁿcⁿ. Следовательно, требуется построить грамматику, порождающую язык { cⁿf ⁿcⁿ | n 1}: S  CFSc | Cfc

FC  CF

Ff  ff

Cf  cf

Cc  cc

КРИТЕРИИ: порождается пустая цепочка: –5

имеется лишняя (непустая) или недостающая цепочка: –10

за каждое лишнее правило: –3 (количество правил в условии дано с запасом)

Замечание. Грамматика S  CFSc | CFc

FC  CF

F  f

C  c ошибочная, так как порождает лишние цепочки, напр.: cfcfcc.

Ответ: (а) Достаточное условие: каждая группа правил с одинаковой левой частью имеет один из перечисленных ниже видов и выполняются дополнительные условия:

1. либо X → ,
   где   (T  N)^* и это единственное правило вывода для этого нетерминала;

2. либо X → a₁₁ | a₂₂ | ... | a_n_n,
   где a_i  T для всех i  1, 2,..., n ; a_i  a_j для i  j; _i  (T  N )^*, т. е. если для нетерминала X правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть попарно различными;

3. либо X → a₁₁ | a₂₂ | ... | a_n_n |  ,
   где a_i  T для всех i  1, 2,..., n; a_i  a_j для i  j; _i  (T  N )^*, и first (X )  follow (X )  .

Замечание. Допускаются обозначения V_T , V_N для обозначения алфавитов терминальных и нетерминальных символов, и обозначение V для их объединения. V  T  N (V V_T  V_N)

(б) нет, не выполняется: т.к. для правила B  cB |  не выполняется условие first (B )  follow (B )  .

[ first (B )  {c}, follow (B )  {a,b,c}  first (B )  follow (B ) {c}≠ ]

КРИТЕРИИ: (а) нет ответа, ошибки в формулировке: –5

(б) нет ответа; неверный ответ; нет обоснования ; ошибочное обоснование: –5

Ответ. Соглашение : запись a является сокращением cout << ′a ′;

L_вх  { c^kb^m| m k  0 }  { c^k b^k b^m-k| m k  0 } (входной язык). Грамматика для L_вх, к которой применим метод рек. спуска, выглядит так:

S  AB

A  cAb |

B  bB | .

L_ц  { ad ^k b^m-k | m k  0 } (целевой язык).

Грамматика с действиями:

КРИТЕРИИ:

Грамматика не порождает L_вх , или не генерирует L_ц : 0

Порождает L_вх и формально генерирует соответствующие цепочки из L_ц ,

но метод рек. спуска неприменим: -5

7. Перечислите этапы технологического цикла создания программного продукта. Кратко охарактеризуйте каждый этап, указав назначение и результат его прохождения.

Ответ:

КРИТЕРИИ: - за каждый пропущенный (крупный) этап, кроме последнего: –2;

- за каждое неверное или отсутствующее пояснение: –1;

- за отсутствие последнего этапа: –1.

8. Перечислите основные типы библиотек, используемых в современных системах программирования (не путать со способами подключения!). Дайте их краткую характеристику.

Ответ: 1. Библиотеки функций (или подпрограмм). 2. Библиотеки классов. 3. Библиотеки компонент.

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

Библиотеки классов - для СП, базирующихся на ООЯП. Все их классы должны быть написаны на том же ЯП, на котором пишется программа, куда интегрируются библиотечные классы.

В библиотеке классов различают конкретные классы, абстрактные классы, шаблоны классов.

Характеристики

Список файлов ответов (шпаргалок)