LL-грамматики по­зволяют построить распознаватели с характеристиками
LL-языки являются собственным подмножеством языков
LR(k)-грамматика является однозначной для
Алгоритм Кока-Янгера-Касами фактически состоит из цик­лов
Алгоритм удаления недостижимых символов строит
Алгоритм Эрли строит
В алгоритме Эрли метасимвол особого вида обозначается
В грамматике G(VT,VN,P,S) вывод вида АÞ*А, AÎVN называется
В конфигурации МП-автомата (q,α,w) q означает
В множество достижимых сим­волов грамматики первоначально входит символ грамматики
В МП-автоматах переходы, при кото­рых входной символ игнорируется, называются
В нормальную форму Хомского можно преобразовать КС-грамматику
В общем виде МП-автомата R(Q,V,Z,d,q0,z0,F) Z означает
В определении грамматики 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)» стоит некоторое число, которое показывает количество
Вопрос об алгоритмической неразрешимости проблем однознач­ности и эквивалентности грамматик сводится к
Все языки программирования определяют нотацию записи
Всякая грамматика операторного предшествования задает язык
Выделяют следующие виды грамматик предшествования: 1) простого; 2) расширенного; 3) сильного; 4) слабого; 5) смешанной стратегии; 6) сложного - из перечисленного
Высший приоритет имеет операция
Грамматика в нормальной форме Грей­бах содержит правила (где aÎVT и αÎVN*)
Грамматика простого предшествования является однозначной
Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терми­нальных символов, носят название
Два МП-автомата называются эквивалентными, если они определяют
Длина цепочки сим­волов обозначается
Длиной цепочки называют количество
Для LR(k)-грамматики порядок чтения входной цепоч­ки символов
Для граммати­ки с фразовой структурой вида G(VT,VN,P,S), V=VNÈVT правила имеют вид
Для классификации самого языка среди всех его грамматик всегда выбирается грамматика с классификационным типом
Для контекстно-зависимых языков распознавателями являются автоматы
Для контекстно-свободных языков распознавателями являются автоматы
Для лю­бого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику
Для минимизации автомата используется алгоритм
Для опе­рации обращения справедливо следующее равенство " α,β
Для операции повторения справедливо следующее равенство " α: α2 =
Для построения вывода по алгоритму Кока-Янгера-Касами грамматика должна быть в нормальной форме
Для построения дерева вывода методом «сверху вниз» используется вывод
Для построения распознавателей LL(k)-грамматик используется множество терминальных цепочек, выводимых из αÎ(VTÈVN)*, укороченных до k символов
Для пре­образования в нормальную форму Хомского предварительно грамматику надо
Для преобразования произвольной КС-грамматики к приведенному виду, необходимо удалить: 1) единичные символы; 2) все бесплодные символы; 3) все недостижимые символы; 4) правила; 5) цепные правила - из перечисленного
Для проверки принадлежности заданного языка классу КС-языков служит лемма о
Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода
Для регулярных языков распознавателями являются автоматы
Для языков с фразовой структурой необходим распознаватель - автомат
Если α = «2334» то αR =
Если α = «23», а β = «34», то αβ =
Если α = β, то
Если α, β и γ - регулярные выражения, то справедлива формула
Если V - некоторый алфавит, то множество всех цепочек над алфавитом V без l
Если V - некоторый алфавит, то множество всех цепочек над алфавитом V, включая l
Если в каждом из состояний конечного автомата для любого входного символа функ­ция перехода содержится не более одного состояния, то конечный авто­мат называют
Если в каждом состоянии конечного автомата сущест­вует функция перехода для всех возможных входных символов, то КА называют
Если в цепочке вывода вида АÞ+αАβ α =l и β¹l, то рекурсия
Если в цепочке вывода вида АÞ+αАβ α =l и β=l, то рекурсия
Если для символа AÎVN в КС-грамматике G(VT,VN,P,S) существует цепочка вывода вида АÞ+αАβ, где α,βÎ(VTÈVN)*, то А называется
Если для символа А в грамматике G определено более одного правила, то процедура разбора ищет среди них правило вида (где aÎVT, γÎ(VNÈVT)*)
Если из нетерминального символа нельзя вывести ни одной цепочки терми­нальных символов, то нетерминальный символ явля­ется
Если из одной и той же его конфигурации МП-автомата возможен более чем один переход, МП-автомат называется
Если функция переходов ДКА определена для каждого состояния автомата, то ДКА называется
Задача разбора заключается в следующем
Из перечисленного для работы алгоритма удаления недостижимых состояний используются множества состояний: 1) недостижимых; 2) достижимых; 3) текущих пассивных; 4) текущих актив­ных
Из перечисленного регу­лярные языки могут быть заданы с помощью: 1) регулярных грамматик; 2) нерегулярных грамматик; 3) конечных автоматов; 4) нерегулярных множеств; 5) регулярных множеств
Из перечисленного: 1) круглые скобки; 2) угловые скобки; 3) квадратные скобки; 4) запятая; 5) точка - в качестве метасимволов для задания грамматик используются
Из перечисленного: 1) ленты; 2) устройства управления; 3) внешней памяти; 4) внутренней памяти; 5) решающего устройства - распознаватель состоит из компо­нентов
Из перечисленного: 1) с символьной структурой; 2) с фразовой структурой; 3) регулярные; 4) нерегулярные; 5) квазирегулярные - существуют типы языков
Из перечисленного: 1) точка входа; 2) центральная точка; 3) нетерминальный символ; 4) узловая точка; 5) вспомогательный символ - при записи правил в графическом виде граф имеет типы вершин
Из расширенного МП-автомата всегда можно построить
Изменение имен символов и подстановки цепочек вместо сим­волов называется
Используются при описании простейших конструкций языков программирования грамматики
Класс грамматик, основанный на принципе выбора одной альтернативы из множества возможных на основе нескольких очередных симво­лов в цепочке, называется
Класс детерминированных КС-языков замкнут относительно операции
Класс детерминированных КС-языков полностью совпадает с классом языков
Класс КС-языков замкнут относительно операции
Когда символ определяется сам через себя в одном правиле, рекурсия называется
Когда символ определяется сам через себя через цепочку правил, рекурсия называется
Конкатенация цепочек α и β обозначает­ся
Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Конфигурацию конечного автомата на каждом шаге работы можно определить в виде (q,w,n), где q
Конфигурация распознавателя определяется параметрами: 1) содержимое выходной цепочки символов; 2) содержимое входной цепочки символов; 3) состояние УУ; 4) содержимое внешней памяти; 5) содержимое внутренней памяти -из перечисленного
КС-грамматика в нормальной форме Хомского сдержит правило для A,B,CÎVN
КС-грамматика в нормальной форме Хомского сдержит правило для AÎVN и aÎVT
Леволинейные автоматные грамматики G(VT,VN,P,S) могут иметь правила видов (где A,BÎVN, tÎVT)
Леволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)
Логика работы распознавателей с возвратом основана на моделировании МП-автомата
Лучшие характеристики среди всех универсаль­ных алгоритмов распознавания входных цепочек для произвольных КС-грамма­тик имеет алгоритм
Любая грамма­тика, допускающая разбор по методу рекурсивного спуска, является
Любая регулярная грамматика является грамматикой
Метасимвол ______________ означает, что из всех перечисленных внутри них цепочек символов в данном месте правила грамматики может стоять только одна це­почка
Минимизация КА заключается в построе­нии эквивалентного КА с меньшим числом
Множества допустимых цепочек символов почти эквивалентных языков могут различаться
Множество конечных конфигураций МП-автомата определяется как
На диаграмме обозначается прямоугольником тип вершины графа
На структуру правил граммати­к с фразовой структурой накладываются ограничения
Наиболее распространенными способами задания грамматик являются: 1) с использованием специальных символов; 2) с использованием метасимволов; 3) в табличном виде; 4) в графическом виде - из перечисленного
Начальная конфигурация МП-автомата определяется как
Недостатком алгоритма рекурсивного спуска является
Непосредственная выводимость цепочки β из цепочки α обозначается
Неукорачивающие грамматики имеют правила вида α®β, где α,βÎV+ и
Нисходящий распознаватель с возвратом моделирует работу МП-автомата
Нисходящий распознаватель с возвратом распознает цепочки языка
Нормальная форма Грейбах является удобной формой представления грамматик для построения распознавателей
Основное отличие УКС-грамматик от НКС-грамматик состоит в том, что
Основной операцией над цепочками символов является операция
По видам памяти распознаватели бывают следующих типов: 1) без внешней памяти; 2) с ограниченной внутренней памятью; 3) с ограниченной внешней памятью; 4) с неограниченной внешней памятью; 5) с неограниченной внутренней памятью - из перечисленного
По видам устройства управления распознаватели подразделяются на: 1) стохастические; 2) алгоритмизированные; 3) детерминированные; 4) недетерминированные; 5) аналитические - из перечисленного
По классификации Хомского выделяют типы грамматик: 1) с фразовой структурой; 2) контекстно-зависимые; 3) дискретные; 4) регулярные; 5) общие - из перечисленного
По столбцам управляющей таблицы для распознавателя LR(k)-грамматик распределены все терминальные и нетерминальные символы грамматики в части
Правила грамматики строятся так, чтобы в левой части каждого правила
Праволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)
Практического применения не имеют грамматики, относящиеся только к типу
При выполнении такта МП-автомата в стеке удаляется
При выполнении такта МП-автомата добавляется
При записи правил в графическом виде вся грамматика представляется в форме
При построе­нии предложений языка, заданного грамматикой, любая цепочка символов мо­жет быть заменена на цепочку символов не меньшей длины в грамматиках
При построении дерева вывода сверху вниз в корень дерева помещается символ
При построении предложений нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста в грамматиках
Приве­денные грамматики называют КС-грамматиками в виде
Проблема однозначности разрешима для класса языков
Произвольную последовательность символов, записанных один за другим, называют
Пустая цепочка обозначается
Работа конечного автомата представляет собой
Распознаватель для грамматик предшествования строится на основе алго­ритма
Самые эффективные с точки зрения требуемых вычис­лительных ресурсов универсальные алгоритмы для распознавания цепочек КС-языков распознаватели
Самый примитивный для КС-языков тип распознавателей
Самыми сложными являются языки
Символы, которые входят в алфавит языка, порождаемого грамматикой, содер­жит
Синтаксический распознаватель цепочек любого языка про­граммирования может быть построен на основе
Укорачивающие контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
Управляющая таблица для распознавателя LR(k)-грамматик состоит из частей: 1) действия; 2) правила; 3) пере­ходы; 4) объекты - из перечисленного
Формальные грамматики классифицируются
Целями преобразований КС-грам­матик являются: 1) упрощение правил грамматики; 2) облегчение создания распознавателя языка; 3) сокращения количества символов; 4) облегчение восприятия человеком - из перечисленного
Цепочка β = d1gd2 называется непосредственно выводимой из цепочки α = d1wd2 в грамматике G(VT,VN,P,S), V = VTÈVN, d1,g,d2ÎV*, wÎV+, если в граммати­ке G существует правило
Цепочка u = FIRST(k,α) носит в работе автомата название
Широко используются при описании синтаксических конструк­ций языков программирования грамматики
Элементами таблицы алгоритма Кока-Янгера-Касами являются множества
Язык, определяемый МП-автоматом R, обо­значается
Языки ассемблеров строятся на основе языков
Языки операторного предшествования являются собствен­ным подмножеством языков
Языки простого предшествования являются собственным подмножеством языков
(αβ)γ =