09.22 Контрольная
4 темы (НАМ, МТ, БНФ, СД) × 3 сложности (простая, норм, гроб); гроб на 2 темы (предположительно БНФ и МТ)
- МТ-П Дан алфавит A = {a, b}. Обратить входное слово P. Пример: babbaa → aabbab.
- Подсказка: обработанные символы можно заменять маркерами
- НАМ-П A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе. Ведущие нули можно не удалять.
- БНФ-П Глубиной скобочной системы называется максимальный уровень вложенности скобок. Глубина пустой системы равна нулю. Описать с помощью РБНФ скобочные системы с глубиной не более трех.
- Подсказка: не забывайте про рекурсию
СД-П Постройте одну синтаксическую диаграмму для следующей РБНФ
слово ::= { приставка } корень [суффикс] окончание приставка ::= "за" | "по" | "при" | "под" | "от" корень ::= "верт" | "крут" | "прыг" | "дрыг" суффикс ::= "ун" | "яч" | "ыш" | "ал" окончание ::= "ка" | "ец" | "ок" | "ня"
- МТ-Н A={ | }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, если является, или слово из одной палочки иначе.
- НАМ-Н A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2ⁿ.
БНФ-Н Наблюдатель смотрит в одну из сторон света — Ю, В, С или З. Каждый час он поворачивается на 90° по- или против часовой стрелки. Напишите БНФ для журнала наблюдений — последовательности сторон света, в которые он смотрел.
Примеры журнала: СЗЮВЮЗЮВСВСЗЮ, Ю, СЗ
СД-Н Тайский боевой корабль симметричен и состоит из (снаружи внутрь): одной или нескольких пар солнечных батарей "<>" или "||", крыльев "-" или "=" ненулевой длины, и одного или нескольких корпусов "0". В каждом корабле используется только один тип солнечных батарей и один тип крыльев. Примеры:
|-0-| <<<==00==>>>
Постройте СД тайского боевого корабля. Нетерминалы можно задавать отдельно.
МТ-Г Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
- БНФ-Г Жизнь человека делится на годы. В первый год он рождается (Р). Далее следуют удачные (У) и неудачные (Н) годы. В жизни удачные и неудачные годы должны быть в одинаковом количестве. Опишите жизнь при помощи БНФ.