Выполните итерацию цепочки (ab)2
b=sd, a=zx, (ab)2= __________
Если КС-грамматика не является леворекурсивной и в ее множестве правил присутствуют только правила вида
А®аa, S®l, причем S не должно встречаться в правых частях других правил, то такая грамматика называется
Если КС-грамматика содержит только правила вида:
A®BС
А®а
S®l, причем S не должно встречаться в правых частях других правил, то эта грамматика называется
LL-грамматики позволяют построить распознаватели с характеристиками
LL-языки являются собственным подмножеством языков
LR(k)-грамматика является однозначной для
Автомат, который может заменять цепочку символов конечной длины в верхней части стека на другую цепочку символов конечной длины, называется
Алгоритм Кока-Янгеля-Касами относится к распознавателям
Алгоритм удаления недостижимых символов строит
Алгоритм Эрли строит
В алгоритме Эрли метасимвол особого вида обозначается
В грамматике G(VT,VN,P,S) вывод вида АÞ*А, AÎVN называется
В множество достижимых символов грамматики первоначально входит символ грамматики
В МП-автоматах переходы, при которых входной символ игнорируется, называются
В нормальную форму Хомского можно преобразовать КС-грамматику
В определении грамматики G(VT,VN,P,S) S означает
В определении грамматики G(VT,VN,P,S) VN означает
В определении грамматики G(VT,VN,P,S) VT означает
В определении грамматики G(VT,VN,P,S) Р означает
В основе синтаксических конструкций большинства современных языков программирования лежат языки
В отличие от обычного, расширенный МП-автомат
В формальной записи конечного автомата M(Q,V,d,q0,F) Q означает
Вместо «k» в названии класса грамматики «LL(k)» стоит некоторое число, которое показывает количество
Вопрос об алгоритмической неразрешимости проблем однозначности и эквивалентности грамматик сводится к
Всякая грамматика операторного предшествования задает язык
Выберите свойства, которые верны для регулярных выражений:
Выделяют следующие виды грамматик предшествования
Выполните конкатенацию двух заданных цепочек a= cd, b=nm, ba=__________
Выполните обращение заданной цепочки: a=город. aR= ________
Высший приоритет имеет операция
Грамматика в нормальной форме Грейбах содержит правила (где aÎVT и αÎVN*)
Грамматика простого предшествования является однозначной
Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терминальных символов, носят название «_____»
Два МП-автомата называются эквивалентными, если они определяют
Длина цепочки символов обозначается
Для LR(k)-грамматики порядок чтения входной цепочки символов
Для грамматики с фразовой структурой вида G(VT,VN,P,S), V=VNÈVT правила имеют вид
Для классификации самого языка среди всех его грамматик всегда выбирается грамматика с классификационным типом
Для контекстно-зависимых языков распознавателями являют (ет)ся
Для контекстно-свободных языков распознавателями являют (ет)ся
Для любого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику
Для операции обращения справедливо следующее равенство " α,β
Для построения вывода по алгоритму Кока–Янгера–Касами грамматика должна быть в нормальной форме
Для построения распознавателей LL(k)-грамматик используется множество терминальных цепочек, выводимых из αÎ(VTÈVN)*, укороченных до k символов
Для преобразования в нормальную форму Хомского, предварительно грамматику надо
Для преобразования произвольной КС-грамматики к приведенному виду, необходимо удалить
Для проверки принадлежности заданного языка классу КС-языков служит лемма о
Для работы алгоритма удаления недостижимых состояний используются множества состояний
Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода
Для регулярных языков распознавателями являют (ет)ся
Для языков с фразовой структурой распознавателем являет (ют)ся
Если V – некоторый алфавит, то множество всех цепочек над алфавитом V без l, обозначается
Если V – некоторый алфавит, то множество всех цепочек над алфавитом V, включая l, обозначается
Если α = «2334» то αR =
Если α = β, то
Если в каждом состоянии конечного автомата для любого входного символа функция перехода содержит не более одного состояния, то этот КА называется
Если в каждом состоянии конечного автомата существует функция перехода для всех возможных входных символов, то этот КА называется
Если в цепочке вывода вида АÞ+αАβ α =l и β¹l, то рекурсия
Если в цепочке вывода вида АÞ+αАβ α =l и β=l, то рекурсия
Если для символа А в грамматике G определено более одного правила, то процедура разбора ищет среди них правило вида (где aÎVT, γÎ(VNÈVT)*)
Если из одной и той же его конфигурации МП-автомата возможен более чем один переход, МП-автомат называется
Если на каждом шаге вывода правило грамматики применяется всегда к крайнему левому нетерминальному символу цепочки, то вывод называется __________
Если на каждом шаге вывода правило грамматики применяется всегда к крайнему правому нетерминальному символу цепочки, то вывод называется __________ .
Если ни при какой входной цепочке невозможен переход автомата из начального состояния q0 в состояние q, то состояние q называется
Если символ не встречается ни в одной сентенциальной форме грамматики, то он называется
Если цепочка символов выводима из целевого символа грамматики, то она называется
Если цепочка, полученная в результате вывода, пустая или содержит только терминальные символы, то вывод называется
Задача разбора заключается в следующем
Из расширенного МП-автомата всегда можно построить
Изменение имен символов и подстановки цепочек вместо символов называется
К регулярным относятся следующие виды грамматик
Класс грамматик, основанный на принципе выбора одной альтернативы из множества возможных на основе нескольких очередных символов в цепочке, называется
Класс детерминированных КС-языков замкнут относительно операции
Класс детерминированных КС-языков полностью совпадает с классом языков
Класс КС-языков замкнут относительно операции
Когда символ определяется сам через себя в одном правиле, рекурсия называется
Когда символ определяется сам через себя через цепочку правил, рекурсия называется
Количество символов цепочки называют __________ цепочки
Конечный автомат, у которого имеется стек, называется
Конкатенация цепочек α и β обозначается
Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Контекстно-свободные грамматики, которые не содержат недостижимых и бесплодных символов, циклов и l-правил, – это
Конфигурацию конечного автомата на каждом шаге работы можно определить в виде (q,w,n), где q
Конфигурация распознавателя определяется параметрами
Леволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)
Леволинейные и праволинейные грамматики
Логика работы распознавателей с возвратом основана на моделировании МП-автомата
Лучшие характеристики среди всех универсальных алгоритмов распознавания входных цепочек для произвольных КС-грамматик имеет алгоритм
Любая автоматная грамматика является
Любая грамматика, допускающая разбор по методу рекурсивного спуска, является
Минимизация КА заключается в построении эквивалентного КА с меньшим числом
Множества допустимых цепочек символов почти эквивалентных языков могут различаться на
На структуру правил грамматик с фразовой структурой накладываются ограничения
Набор правил, определяющий допустимые конструкции языка, - это
Найдите правильный результат α2 =
Недостатком алгоритма рекурсивного спуска является
Непосредственная выводимость цепочки β из цепочки α обозначается
Нетерминальный символ, из которого нельзя вывести ни одной цепочки терминальных символов, называется
Неукорачивающие грамматики имеют правила вида α®β, где α,βÎV+ и
Нисходящий распознаватель с возвратом моделирует работу МП-автомата
Нисходящий распознаватель с возвратом распознает цепочки языка
Нормальная форма Грейбах является удобной формой представления грамматик для построения распознавателей
Описание способа построения предложений некоторого языка, – это
Основной операцией над цепочками символов является операция «______»
Перечислите алгоритмы относящиеся к табличным распознавателям
По видам памяти распознаватели бывают следующих типов
По видам устройства управления распознаватели подразделяются на
По столбцам управляющей таблицы для распознавателя LR(k)-грамматик распределены все терминальные и нетерминальные символы грамматики в части
Подсчитайте длину цепочки b=аааа. |b|=___(ответ цифрой)_
Правила грамматики строятся так, чтобы в левой части каждого правила
Правильно охарактеризуйте типы грамматик
Праволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)
При выполнении такта МП-автомата в стеке удаляется
При выполнении такта МП-автомата добавляется
При построении дерева вывода сверху вниз в корень дерева помещается символ
При построении предложений нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста в грамматиках
При построении предложений языка, заданного грамматикой, любая цепочка символов может быть заменена на цепочку символов не меньшей длины в грамматиках
Приведенные грамматики называют КС-грамматиками в виде
Проблема однозначности разрешима для класса языков
Произвольную последовательность символов, записанных один за другим, называют
Процесс порождения предложения языка на основе правил, определяющих язык грамматики, называется ____________ .
Процесс построения эквивалентного конечного автомата с меньшим числом состояний называется
Пустая цепочка может обозначаться
Работа конечного автомата представляет собой
Раздел языка, определяющий значение предложений языка, – это
Распознаватель для грамматик предшествования строится на основе алгоритма
Распознаватель состоит из следующих основных компонентов
Регулярные языки могут быть заданы при помощи
Самые эффективные (с точки зрения требуемых вычислительных ресурсов) и универсальные алгоритмы для распознавания цепочек КС-языков, – это
Самый примитивный для КС-языков тип распознавателей – это
Самыми сложными являются языки
Символ А в КС-грамматике, для которого существует цепочка вывода вида А+aAb, называется
Символы, которые входят в алфавит языка, порождаемого грамматикой, называются
Символы, которые содержат слова, понятия, конструкции языка, называются
Синтаксический распознаватель цепочек любого языка программирования может быть построен на основе
Совокупность слов языка, это
Счетное множество допустимых символов языка, – это
Укажите выражение, тождественное данному: (αβ)γ =
Укорачивающие контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Управляющая таблица для распознавателя LR(k)-грамматик состоит из частей
Формальные грамматики классифицируются по
Целями преобразований КС-грамматик являются
Цепочка u = FIRST(k,α) носит в работе автомата название
Широко используются при описании синтаксических конструкций языков программирования грамматики
Элементами таблицы алгоритма Кока–Янгера–Касами являются множества
Языки ассемблеров строятся на основе языков
Языки операторного предшествования являются собственным подмножеством языков
Языки простого предшествования являются собственным подмножеством языков