Формальные языки и грамматики. Часть 1

Правильно охарактеризуйте типы грамматик

• тип 2: контекстно-свободные грамматики
• имеют правила вида: 1) А®Вg или А®g 2) А®gВ или А®g
• тип 1: контекстно-зависимые и неукорачивающие грамматики
• на правила грамматики не накладывается никаких ограничений: a®b
• тип 0: грамматики с фразовой структурой
• имеют правила вида a1Аa2®a1ba2 и a®b, где |b| ³ |a|
• тип 3: регулярные грамматики
• имеют правила вида: А®b

Для контекстно-свободных языков распознавателями являют (ет)ся

• двусторонние недетерминированные автоматы
• конечные автоматы
• односторонние недетерминированные автоматы
• машина Тьюринга

В определении грамматики G(VT,VN,P,S) VN означает

• множество нетерминальных символов
• множество правил грамматики
• множество терминальных символов
• целевой символ грамматики

Изменение имен символов и подстановки цепочек вместо символов называется

• гомоморфизмом
• конкатенациями
• гетероморфизмом
• дополнениями

Для регулярных языков распознавателями являют (ет)ся

• двусторонние недетерминированные автоматы
• конечные автоматы
• односторонние недетерминированные автоматы
• машина Тьюринга

Вместо «k» в названии класса грамматики «LL(k)» стоит некоторое число, которое показывает количество

• символов алфавита соответствующего языка
• нетерминальных символов
• рассматриваемых символов для однозначного выбора альтернативы
• правил грамматики

Для классификации самого языка среди всех его грамматик всегда выбирается грамматика с классификационным типом

• наиболее удобным для описания
• минимально возможным
• максимально возможным
• любым возможным

В основе синтаксических конструкций большинства современных языков программирования лежат языки

• квазирегулярные
• с фразовой структурой
• КС
• регулярные

Символ А в КС-грамматике, для которого существует цепочка вывода вида А+aAb, называется

• рекурсивным
• бесплодным
• цепным
• недостижимым

Найдите правильный результат α2 =

• αα
• αRαR
• α+α
• α*α

Конфигурацию конечного автомата на каждом шаге работы можно определить в виде (q,w,n), где q

• текущее состояние автомата
• конечное состояние автомата
• цепочка входных символов
• положение указателя в цепочке символов

Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода

• слева направо
• сверху вниз
• справа налево
• снизу вверх

Языки операторного предшествования являются собственным подмножеством языков

• простого предшествования
• недетерминированных КС
• регулярных
• LR

Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терминальных символов, носят название «_____»

• LL(k)-нетерминальные
• сильно LL(k)-грамматики
• LL(k)-терминальные
• правосторонние LL(k)-грамматики

Выделяют следующие виды грамматик предшествования

• расширенного
• составного
• слабого
• простого

Если в каждом состоянии конечного автомата существует функция перехода для всех возможных входных символов, то этот КА называется

• детерминированным
• полностью определенным
• однозначным
• недетерминированным

К регулярным относятся следующие виды грамматик

• контекстно-зависимые
• автоматные
• праволинейные
• леволинейные

Символы, которые содержат слова, понятия, конструкции языка, называются

• целевыми
• терминальными
• нетерминальными
• метасимволами

Алгоритм Эрли строит

• совокупность правил
• последовательность списков ситуаций
• таблицу
• множество объектов

Самые эффективные (с точки зрения требуемых вычислительных ресурсов) и универсальные алгоритмы для распознавания цепочек КС-языков, – это

• МП-автомат
• табличные распознаватели
• сдвиг-свертка
• нисходящий распознаватель с возвратом

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

• L(kr)
• LL(k)
• RR(k)
• LLR

LL-языки являются собственным подмножеством языков

• LR
• простого предшествования
• недетерминированных КС
• регулярных

Формальные грамматики классифицируются по

• степени контекстной зависимости
• степени сложности
• структуре их языков
• структуре их правил

Укорачивающие контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида

• А®β, где AÎVN, βÎV*
• А®β, где AÎVN, βÎV+
• А®Аβ, где AÎVN, βÎV+
• А®β, где AÎV+, βÎVN

Если α = β, то

• |α| = β
• |α| = |β|
• α =|α +β|
• α = |β|

Подсчитайте длину цепочки b=аааа. |b|=___(ответ цифрой)_

Если V – некоторый алфавит, то множество всех цепочек над алфавитом V, включая l, обозначается

• V*
• V+
• V+l
• V*l

Для любого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику

• регулярную
• постоянную
• неукорачивающую
• ограниченную

Если в цепочке вывода вида АÞ+αАβ α =l и β=l, то рекурсия

• представляет собой цикл
• является правой
• является левой
• представляет собой рекурсию

Если α = «2334» то αR =

• «4»
• «4332»
• «2334»
• «23342334»

Для грамматики с фразовой структурой вида G(VT,VN,P,S), V=VNÈVT правила имеют вид

Для построения вывода по алгоритму Кока–Янгера–Касами грамматика должна быть в нормальной форме

• Кока–Янгера–Касами
• Кока–Янгера
• Янгера–Касами
• Хомского

Выберите свойства, которые верны для регулярных выражений:

Алгоритм Кока-Янгеля-Касами относится к распознавателям

• с возвратом
• нисходящим
• на основе сдвиг-свертка
• табличным

Выполните обращение заданной цепочки: a=город. aR= ________

Конкатенация цепочек α и β обозначается

• |αβ|
• αβ
• α+β
• α*β

В формальной записи конечного автомата M(Q,V,d,q0,F) Q означает

• конечное множество допустимых входных символов
• функцию переходов
• начальное состояние автомата
• конечное множество состояний автомата

При построении предложений нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста в грамматиках

• НКС
• КЗ
• УКС
• КС

Счетное множество допустимых символов языка, – это

• цепочка
• грамматика
• слово
• алфавит

В определении грамматики G(VT,VN,P,S) S означает

• множество терминальных символов
• целевой символ грамматики
• множество нетерминальных символов
• множество правил грамматики

При выполнении такта МП-автомата в стеке удаляется

• верхний символ
• цепочка, соответствующая правилу перехода
• нижний символ
• цепочка метасимволов

Из расширенного МП-автомата всегда можно построить

• эквивалентный ему ДМП-автомат
• МП-грамматику
• эквивалентный ему обычный МП-автомат
• МП-язык

Леволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)

• А®Вγ или А®АВγ
• А®γВ или А®γ
• А®Вγ или А®γ
• А®Вγ или А®В

Установите соответствие

• для контекстно-свободных языков распознавателями являются
• конечные автоматы
• для языков с фразовой структурой распознавателем является
• двусторонние недетерминированные автоматы
• для контекстно-зависимых языков распознавателями являются
• машина Тьюринга
• для регулярных языков распознавателями являются
• односторонние недетерминированные автоматы

Символы, которые входят в алфавит языка, порождаемого грамматикой, называются

• метасимволами
• нетерминальными
• терминальными
• целевыми

Если цепочка, полученная в результате вывода, пустая или содержит только терминальные символы, то вывод называется

• законченным
• сентенциальным
• последовательным
• рекурсивным

Пустая цепочка может обозначаться

• 0

Совокупность слов языка, это

• синтаксис языка
• лексика языка
• семантика языка
• грамматика языка

Цепочка u = FIRST(k,α) носит в работе автомата название

• начальная
• первичная
• базовая
• аванцепочка

Укажите выражение, тождественное данному: (αβ)γ =

• α|βγ|
• γ(αβ)
• α(βγ)
• (βα)γ