Список вопросов базы знаний

Если для символа 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) аналитические - из перечисленного