Главная /
Алгоритмы и дискретные структуры /
Математическая теория формальных языков
Математическая теория формальных языков - ответы на тесты Интуит
Правильные ответы выделены зелёным цветом.
Все ответы: Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.
Все ответы: Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.
Смотрите также:
Используемые в приложениях формальные языки
(1) являются конечными
(2) являются бесконечными
(3) как правило, не определяются понятием конечности
Контекстно-свободным грамматикам соответствуют
(1) конечные автоматы
(2) автоматы с магазинной памятью
(3) бесконечные детерминированные автоматы
Замкнутость класса контекстно-свободных языков бывает
(1) относительно деления
(2) относительно взятия гомоморфного образа
(3) относительно полного гомоморфного прообраза
Теорема о детерминизации
(1) не переносится с конечных автоматов на автоматы с магазинной памятью
(2) одинакова для конечных автоматов и автоматов с магазинной памятью
(3) неприменима к автоматам с магазинной памятью
Процесс нахождения дерева вывода слова в заданной контекстно-свободной грамматике называется
(1) синтаксическим анализом
(2) синтаксической интерполяцией
(3) синтаксическим разбором
В понятие машины Тьюринга входит
(1) множество состояний
(2) входной алфавит
(3) внешний алфавит
Эквивалентный способ задания языка
(1) не важен
(2) важен
(3) не определяется, как понятие
Алгоритмические проблемы, связанные с контекстно-свободными языками
(1) все до единой разрешимы
(2) иногда бывают неразрешимыми
(3) не имеют решения
К наиболее распространенным способам конечного задания формального языка относят
(1) грамматики
(2) автоматы
(3) порождающие выражения
Чтобы выяснить, является ли некоторый формальный язык автоматным, нужно
(1) применять специальные средства, позволяющие это выяснять
(2) проверить наличие в нем пустых слов
(3) определить количество символов алфавита
Класс всех автоматных языков относительно взятия гомоморфного образа
(1) замкнут
(2) не определен
(3) обобщен
Наиболее удобным и компактным способом конечного описания формального языка являются
(1) грамматики
(2) автоматы
(3) регулярные выражения
Если соответствующее отношение взаимозаменяемости разбивает множество всех слов рассматриваемого алфавита на конечное число классов эквивалентности, то
(1) язык является автоматным
(2) язык нельзя назвать автоматность
(3) невозможно определить автоматностьи
Контекстно-свободные языки используются
(1) в компиляторах
(2) в средствах форматирования исходного кода
(3) в системах верстки
Каждая контекстно-свободная грамматика по отношению к некоторой контекстно-свободной грамматике специального вида
(1) эквивалентна
(2) эквипотенциальна
(3) не определена
Класс контекстно-свободных языков
(1) не замкнут относительно дополнения и пересечения
(2) замкнут относительно дополнения и пересечения
(3) не определяется относительно дополнения и пересечения
Каждая грамматика порождает
(1) как минимум пару языков
(2) не меньше четырех языков
(3) только один язык
Автоматы бывают
(1) конечными
(2) аддитивными
(3) с магазинной памятью
Замкнутость класса контекстно-свободных языков относительно деления
(1) отличается от замкнутости относительно взятия гомоморфного образа
(2) совпадает с замкнутостью относительно взятия гомоморфного образа
(3) не имеет смысла
В ходе применения теоремы о детерминизации на автоматах с магазинной памятью возникает
(1) класс языков, такой же, как и для конечных автоматов
(2) класс языков, распознаваемых детерминированными автоматами с магазинной памятью
(3) система формирования языков
Последовательность правил, примененных при выводе в контекстно-свободной грамматике, называется
(1) приоритет
(2) протокол
(3) порядок вывода
Такт работы машины Тьюринга представляет собой
(1) биквадратное отношение
(2) бинарное отношение
(3) интерполяционную зависимость
Порождающая грамматика бывает
(1) интерполяционной
(2) аддитивно-инъективной
(3) неукорачивающей
Проблема пустоты пересечения контекстно-свободных языков
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Для конструирования распознающих устройств, пригодных для практических приложений подходят
(1) все конечные автоматы
(2) не все конечные автоматы
(3) все бесконечные автоматы
Достаточные условия автоматности применимы для
(1) выяснения, является формальный язык автоматным
(2) выяснения, является формальный язык контекстным
(3) проверки наличия пустых слов в алфавите
Среди языков, не содержащих пустого слова, автоматными являются
(1) образы локальных языков при побуквенных гомоморфизмах
(2) образы локальных языков при локальных гомоморфизмах
(3) все контекстные языки
В регулярных выражениях используются символы, обозначающие
(1) итерацию
(2) конкатенацию
(3) объединение языков
Классы эквивалентности по взаимозаменяемости относительно автоматного языка
(1) не определены
(2) независимы
(3) сами являются автоматными языками
Все праволинейные языки принадлежат к
(1) подклассу с многозначной грамматикой
(2) подклассу с однозначной грамматикой
(3) подклассу с не определенной грамматикой
Приведение контекстно-свободной грамматики к нормальной форме Грейбах
(1) возможно
(2) невозможно
(3) не имеет практического применения
Лемма о разрастании для контекстно-свободных языков формализует
(1) явление "периодичности" в этих языках
(2) явление "инъективности" в этих языках
(3) явление "нестабильности" в этих языках
Натуральными числами принято называть
(1) все целые числа
(2) только неотрицательные целые числа
(3) все числа,как отрицательные, так и положительные
Автомат с магазинной памятью
(1) отличается от конечного автомата наличием потенциально бесконечной памяти
(2) отличается от конечного автомата отсутствием потенциально бесконечной памяти
(3) ничем не отличается от конечного автомата
Для гомоморфизма и связанного с ним определенным отношением контекстно-свободного языка
(1) существует контекстно-свободный язык
(2) не существует контекстно-свободного языка
(3) не имеет смысла наличие контекстно-свободного языка
Детерминированные автоматы с магазинной памятью - это автоматы с магазинной памятью, которые
(1) ни в какой конфигурации не могут выбирать между несколькими очередными тактами
(2) в любой конфигурации могут выбирать между несколькими очередными тактами
(3) в любой конфигурации сами определяют все такты сразу
Разным левосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют
(1) все целые числа
(2) пустые протоколы
(3) разные протоколы
Машины Тьюринга можно изображать в виде
(1) интерполяционных зависимостей
(2) аддитивных преобразований
(3) диаграмм
Каждая контекстная грамматика
(1) является неукорачивающей
(2) не является неукорачивающей
(3) не может быть определена понятием неукорачиваемости
Проблема однозначности контекстно-свободной грамматики
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Конечные автоматы можно изображать в виде
(1) двумерного массива данных
(2) диаграмм состояний
(3) трехмерного массива данных
Свойства замкнутости класса всех автоматных языков
(1) можно использовать как достаточные условия автоматности
(2) не используют как достаточные условия автоматности
(3) не имеет смысла использовать как достаточные условия автоматности
Установка числового критерия автоматности для языков над однобуквенным алфавитом
(1) возможна
(2) невозможна
(3) практически не применима
Регулярные выражения применяются в
(1) текстовых редакторах
(2) интерпретаторах командной строки
(3) программных средствах обработки трехмерной графики
Любой минимальный полный детерминированный конечный автомат, распознающий заданный язык
(1) инъективен этому автомату
(2) конъюктивен этому автомату
(3) изоморфен этому автомату
Некоторые упорядоченные деревья, вершины которых помечены символами принадлежности алфавиту - это
(1) деревья вывода
(2) деревья ввода
(3) деревья интерполяции
Символ грамматики бывает
(1) бесполезным
(2) порождающим
(3) достижимым
Для любого дерева вывода в грамматике длина кроны дерева
(1) неограниченна
(2) не имеет числовой формы
(3) определяется строго по формулам
Алфавитом называется
(1) конечное непустое множество
(2) бесконечное непустое множество
(3) бесконечный набор символов, имеющих общие признаки
Потенциально бесконечная память используется
(1) как стек
(2) как буфер обмена
(3) посредством вывода символов в определенной последовательности
Гомоморфизм можно задать
(1) инъективными словами
(2) равенствами
(3) аддитивными символами
Чтобы получить полезный и естественный с точки зрения практики класс языков, нужно
(1) добавить в конец каждого слова специальный символ
(2) изменить каждый символ на противоположный по значению
(3) заменить каждый символ его инверсией
При префиксном обходе упорядоченного дерева в первую очередь посещается
(1) крона
(2) главная ветвь
(3) корень
На диаграмме, изображающей машину Тьюринга
(1) состояние обозначается кружком, а переход - стрелкой
(2) состояние обозначается стрелкой, а переход - кружком
(3) и состояния, и переходы обозначают стрелками
Каждая неукорачивающая грамматика
(1) эквивалентна некоторой контекстной грамматике
(2) обратно инъективна некоторой контекстной грамматике
(3) не может иметь связи с любой контекстной грамматикой
Проблема контекстной свободности дополнения контекстно-свободного языка
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Слово допускается конечным автоматом, если
(1) оно является меткой некоторого успешного пути
(2) оно не является меткой успешного пути
(3) оно не может быть определено сразу
Пересечение автоматных языков является
(1) пустым множеством
(2) автоматным языком
(3) множеством целых чисел
Необходимое условие автоматности
(1) связано с длинами слово
(2) не связано с длинами слов
(3) не определяется длинами сло
Операция итерации имеет приоритет
(1) выше, чем умножение
(2) ниже, чем умножение
(3) такой же, как и у умножения
Состояния полного детерминированного конечного автомата называются различными, если существует слово, которое их
(1) различает
(2) объединяет
(3) заменяет
Корень дерева вывода отвечает
(1) конечному символу
(2) набору значений конечных символов
(3) начальному символу
Множества, определяющие, что в контекстно-свободной грамматике нет бесполезных символов
(1) реально существуют
(2) не существуют
(3) не определяются
Если количество вершин в самом длинном пути равно 4, то длина кроны дерева вывода равна
(1) 4
(2) 8
(3) 16
Конечная последовательность элементов алфавита называется
(1) словом
(2) цепочкой
(3) строкой
Бесконечная память представляет собой
(1) структуру данных
(2) последовательность символов и пустых слов
(3) многомерный массив числовых данных
Постановка каждому символу в соответствие конечный язык
(1) невозможна
(2) возможна
(3) не имеет практического смысла
Маркером конца слова по своей сути является
(1) пустое множество
(2) символ
(3) итерационная последовательность символов
Левым разбором слова в контекстно-свободной грамматике называется
(1) протокол любого левостороннего вывода слова в грамматике
(2) получение итерации результата левостороннего вывода
(3) получение инъективного левостороннего вывода
Машина Тьюринга
(1) способна вычислять функции
(2) неспособна вычислять функции
(3) не работает с функциями
При определенных условиях линейно ограниченным автоматом называют
(1) инъективно неопределенную грамматику
(2) грамматику пустых слов
(3) машину Тьюринга
Язык, согласно определению
(1) может быть непустым
(2) должен быть итерационно определенным
(3) не может быть непустым
Два конечных автомата, распознающих один и тот же язык, называются
(1) одномерными
(2) эквивалентными
(3) эквипотенциальными
Лемма о разрастании позволяет установить
(1) неавтоматность формального языка
(2) неконтекстность формального языка
(3) неординарность формального языка
При определенных условиях для любого гомоморфизма и автоматного языка можно
(1) оценить их взаимоиспользование
(2) составить однородный контекстный язык
(3) составить автоматный язык
Каждое регулярное выражение над алфавитом задает
(1) некоторый язык над алфавитом
(2) некоторое целое подмножество над алфавитом
(3) определенную последовательность натуральных чисел над алфавитом
Удалив из минимального полного детерминированного конечного автомата бесполезное состояние, получим
(1) минимальный детерминированный конечный автомат
(2) максимальный детерминированный конечный автомат
(3) оптимальный детерминированный конечный автомат
Каждому символу слова, которым заменяется начальный символ на первом шаге вывода, ставится в соответствие
(1) ветвь дерева
(2) вершина дерева
(3) корень дерева
Грамматика в нормальной форме Хомского
(1) контекстно-свободная грамматика
(2) контекстно-определяемая грамматика
(3) контекстно-неопределимая грамматика
Каждая линейная грамматика по отношению к линейной грамматике в нормальной форме
(1) эквивалентна
(2) апериодична
(3) периодична
Над языками можно производить операции
(1) объединения
(2) пересечения
(3) разности
При формальном определении конфигурации автомата с магазинной памятью считают все содержимое стека
(1) конечной последовательностью символов
(2) бесконечной последовательностью символов
(3) словом
Критерии контекстной свободности
(1) существуют
(2) отсутствуют
(3) не определяются
Автомат с магазинной памятью называется детерминированным, если
(1) имеет ровно одно начальное состояние
(2) все переходы этого автомата попарно несовместны
(3) имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны
Процесс нахождения левого разбора слова в заданной контекстно-свободной грамматике называется
(1) восходящим разборомя
(2) нисходящим разбором
(3) усредненным разбором
Машина Тьюринга
(1) способна вычислять частичные функции
(2) неспособна вычислять частичные функции
(3) не работает с частичными функциями
Класс контекстных языков замкнут относительно
(1) объединения
(2) пересечения
(3) дополнения
Алгоритм, позволяющий по произвольной контекстно-свободной грамматике узнать, является ли грамматика однозначной
(1) не существует
(2) существует
(3) применяется только в самых сложных случаях
Автоматными являютсяи
(1) все конечные языки
(2) только определенный класс конечных языков
(3) только однородные конечные языки
Класс автоматных языков замкнут относительно
(1) итерации
(2) конкатенации
(3) объединения
Задание исходного языка с помощью конечного автомата
(1) возможно
(2) невозможно
(3) не имеет смысла
Обобщенным конечным автоматом можно назвать
(1) аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями
(2) конечный автомат, использующий контекстные выражения
(3) автомат, реализующий проверку наличия пустых слов в языке
Множество контекстов и множество двусторонних контекстов
(1) различны
(2) одинаковы
(3) не связаны друг с другом
Слово, записанное в вершинах, помеченных символами из алфавита, называется
(1) веткой
(2) кроной
(3) стволом
Грамматика в нормальной форме Грейбах является
(1) контекстно-неопределенной грамматикой
(2) контекстно-зависимой грамматикой
(3) контекстно-свободной грамматикой
Если линейный язык не содержит пустого слова, то он
(1) порождается некоторой линейной грамматикой в нормальной форме
(2) игнорируется любой грамматикой
(3) не рассматривается, как порождаемый линейной грамматикой в нормальной форме
Слово, в котором символы, составляющие слово, идут в обратном порядке называют
(1) зеркальным образом
(2) обращением
(3) перевертышем
С понятием автомата с магазинной памятью связывают
(1) входной алфавит
(2) алфавит магазинной памяти
(3) множество переходов
Возможно ли определение критериев контекстной свободности?
(1) нет
(2) да
(3) неизвестно
Детерминированным контекстно-свободным языком является
(1) каждый автоматный язык
(2) только инъективный автоматный язык
(3) единственно аддитивный автоматный язык
Конечную последовательность конфигураций автомата с магазинной памятью, каждая из которых получается из предыдущей одним тактом работы автомата, называют
(1) вычислительным процессом
(2) методической итерацией
(3) аддитивной конъюнкцией
Машина Тьюринга может быть
(1) в допускающем состоянии
(2) в отвергающем состоянии
(3) в аддитивном состоянии
Замкнутость относительно операции объединения
(1) очевидна
(2) не доказана
(3) не имеет смысла
Грамматика является неоднозначной тогда и только тогда, когда
(1) постовская система соответствия имеет решение
(2) постовская система соответствия не имеет решения
(3) постовская система соответствия не определена
Конфигурация представляет собой
(1) набор цифровых символов, имеющих строгую последовательность
(2) двумерный массив чисел, задающий положение символов
(3) "мгновенное описание" конечного автомата
Каждый из исходных языков задан конечным автоматом
(1) с одним начальным и двумя заключительными состояниями
(2) с одним начальным и одним заключительным состоянием
(3) с двумя начальными и одним заключительным состоянием
Гомоморфизм может быть
(1) побуквенным
(2) билинейным
(3) итерационным
Если слово принадлежит языку, задаваемому меткой некоторого успешного пути, то оно
(1) допускается обобщенным конечным автоматом
(2) игнорируется обобщенным конечным автоматом
(3) не учитывается при составлении алфавита
Полугруппа - это
(1) непустое множество с ассоциативной бинарной операцией
(2) пустое множество без ассоциативной бинарной операции
(3) множество отрицательных значений любого множества
Правосторонний и левосторонний вывод определяются
(1) по одинаковым принципам
(2) абсолютно по-разному
(3) не имеют определения
Построение грамматики "почти в нормальной форме Грейбах"
(1) возможно
(2) не возможно
(3) не реализуется из-за сложности расчетов
Объединение линейных языков
(1) является линейным языком
(2) не является линейным языком
(3) не имеет смысла, как действие
Элементы основного алфавита называются
(1) основными буквами
(2) терминальными символами
(3) итерационными символами
Автоматы с магазинной памятью можно изображать с помощью
(1) диаграмм состояний
(2) диаграмм соответствия
(3) интерполяционных диаграмм
Имея два языка, связанных между собой
(1) мы можем найти определенный гомоморфизм
(2) мы не сможем определить ни одного гомоморфизма
(3) можно сделать предположение о невозможности определенным образом составить гомоморфизм
Эквивалентность автоматов с магазинной памятью доказывается с помощью
(1) индукции по сумме избытков всех переходов
(2) конъюнкции по частному избытков всех переходов
(3) дизъюнкции по разности избытков всех переходов
Грамматика может обладать
(1) аддитивно-итерационной формой
(2) конъюктивно-итерационной формой
(3) сентенциальной формой
Если существует детерминированная машина Тьюринга, то язык над алфавитом называется
(1) разрешенным
(2) рекурсивным
(3) аддитивным
Алгоритм, позволяющий по контекстно-свободной грамматике узнать, бесконечен ли язык
(1) не определен
(2) существует
(3) не имеет практического применения
"Раскрытием" определенных вспомогательных символов можно получить
(1) итерационно-независимую грамматику
(2) линейную грамматику
(3) аддитивно-независимую грамматику
Каждый автоматный язык является
(1) праволинейным
(2) контекстным
(3) корректно-линейным
Класс автоматных языков замкнут относительно
(1) дополнения
(2) обобщения
(3) пересеченияи
Язык может быть
(1) глобальным
(2) локальным
(3) централизованным
Преобразовать конечный автомат в обобщенный конечный автомат можно
(1) заменив в метках переходов пустое слово на 1, а каждое непустое слово - на сумму его букв
(2) заменив в метках переходов пустое слово на 0, а каждое непустое слово - на произведение его букв
(3) заменив в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв
Полугруппа с единицей, принадлежащей множеству, называется
(1) моноид
(2) итерационная подгруппа
(3) инъективная группа
Если существует слово, которое имеет два или более левосторонних вывода, то контекстно-свободная грамматика называется
(1) неоднозначной
(2) недопустимой
(3) нестабильной
Укажите верное утверждение:
(1) каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах
(2) каждая контекстно-свободная грамматика пропорциональна некоторой грамматике в нормальной форме Грейбах
(3) каждая контекстно-свободная грамматика эквипотенциальна некоторой грамматике в нормальной форме Грейбах
Произведение контекстно-свободных языков дает в итоге
(1) контекстно-свободный язык
(2) контекстно несвободный язык
(3) итерацию простых автоматов
Грамматика может быть
(1) контекстно-свободной
(2) линейной
(3) контекстной
Язык, распознаваемый автоматом с магазинной памятью - это
(1) множество всех слов, допускаемых этим автоматом
(2) множество всех слов
(3) пустое множество
Укажите, какое утверждение является неверным:
(1) некоторые свойства контекстно-свободных языков удобно доказывать с привлечением автоматов с магазинной памятью
(2) к свойствам замкнутости класса контекстно-свободных языков относится замкнутость относительно деления
(3) к свойствам замкнутости класса контекстно-свободных языков не относят замкнутость относительно взятия гомоморфного образа
Детерминированый контекстно-свободный язык
(1) является существенно неоднозначным
(2) не является существенно однозначным
(3) не определяется понятием однозначности
Устранение из грамматики бесполезных символов
(1) возможно
(2) невозможно
(3) не применяется на практике
Язык, допускаемый машиной Тьюринга - это
(1) язык, состоящий из всех допускаемых данной машиной Тьюринга слов
(2) язык, состоящий из всех необрабатываемых данной машиной Тьюринга слов
(3) последовательность слов, которые не используются без пустого слова
Язык является конечным, если
(1) грамматика не содержит "рекурсивных" нетерминальных символов
(2) грамматика содержит "рекурсивные" нетерминальные символы
(3) грамматика содержит "нерекурсивные" терминальные символы
Дополнение языка является непустым тогда и только тогда, когда постовская система соответствия
(1) имеет решение
(2) не имеет решения
(3) не определена
Полным детерминированным конечным автоматом
(1) распознается каждый автоматный язык
(2) не распознаются автоматные языки
(3) не имеет смысла производить распознавание автоматного языка
Пересечение выражается через
(1) объединение и дополнение
(2) итерацию и конкатенацию
(3) дополнение, объединение и конкатенацию
Автоматным является
(1) каждый локальный язык
(2) только однородный локальный язык
(3) любой язык вообще
Язык является регулярным тогда и только тогда, когда он является
(1) независимым
(2) неоднородным
(3) автоматным
Если язык является автоматным, то синтаксический моноид
(1) бесконечен
(2) конечен
(3) не определен
Если не существует слова, которое имеет два или более левосторонних вывода, то контекстно-свободная грамматика называется
(1) однозначнойй
(2) нестабильной
(3) неоднозначной
Определите неверное утверждение из нижеприведенных:
(1) замена терминального символа на нетерминальный возможна
(2) замена одной грамматики на другую может производиться при необходимости
(3) замена терминального символа на нетерминальный невозможна
Объединение линейных языков
(1) является линейным языком
(2) не является линейным языком
(3) не имеет смысла, как действие
Способ конечного описания формального языка
(1) необходим
(2) не нужен
(3) не описывается по практическим соображениям
Автоматы с магазинной памятью соответствуют
(1) контекстно-свободным грамматикам
(2) праволинейным грамматикам
(3) как контекстно-свободным, так и праволинейным грамматикам
Замкнутость относительно деления
(1) не является свойством замкнутости класса контекстно-свободных языков
(2) является свойством замкнутости класса контекстно-свободных языков
(3) не имеет смысла по отношению к классу контекстно-свободных языков
Применение теоремы о детерминизации для конечных автоматов к автоматам с магазинной памятью
(1) невозможно
(2) возможно
(3) возможно, но не имеет практического смысла
Синтаксическим анализом называют
(1) процесс нахождения дерева вывода слова
(2) процесс интерполяции дерева вывода слова
(3) процесс итерации дерева вывода слова
К составным частям машины Тьюринга относят
(1) ленточный алфавит
(2) бланк
(3) пустой символ
Эквивалентный способ задания языка, используемый в точной формулировке массовой задачи
(1) не имеет особого значения
(2) имеет огромное значение
(3) не используется
Язык может быть представлен
(1) только контекстно-свободной грамматикой
(2) только с помощью автоматов с магазинной памятью
(3) как с помощью автоматов с магазинной памятью, так и с помощью контекстно-свободной грамматики
Автоматами называют
(1) математические модели вычислительных устройств
(2) вычислительные устройства
(3) программы, осуществляющие кодировку алфавита
Для практического применения теории конечных автоматов
(1) необходимо рассчитать позицию каждого символа в языке
(2) нужно применить специальные средства, определяющие, является ли некоторый формальный язык автоматным
(3) нужно учесть появление побочных символовм
Относительно взятия гомоморфного образа
(1) класс всех автоматных языков является замкнутым
(2) определяются критерии однозначности
(3) происходит оценка достоверности
Регулярные выражения представляют собой
(1) наиболее удобный и компактный способ описания формального языка
(2) наиболее трудоемкий способ описания формального языка
(3) наиболее неудобный и неудачный способ описания формального языка
Построить минимальный детерминированный конечный автомат для заданного языка позволяют
(1) соответствующие классы эквивалентности
(2) методы уравнивания символов
(3) способы детерминации
В программных средствах форматирования исходного кода в основном используют
(1) контекстно-свободные языки
(2) автоматы
(3) грамматики
Эквивалентной по отношению к некоторой контекстно-свободной грамматике специального вида является
(1) только ограниченная контекстно-свободная грамматика
(2) каждая контекстно-свободная грамматика
(3) потенциальная контекстно-свободная грамматика
Относительно дополнения и пересечения класс контекстно-свободных языков
(1) замкнут
(2) не замкнут
(3) инъективен
Каждому языку, который порождается хотя бы одной грамматикой, соответствует
(1) бесконечное множество грамматик
(2) две грамматики
(3) одна грамматика
Автоматы с магазинной памятью
(1) ничем не отличаются от конечных автоматов
(2) абсолютно отличаются от конечных автоматов
(3) являются итерационными автоматами
Замкнутость относительно взятия гомоморфного образа
(1) отличается от замкнутости относительно взятия полного гомоморфного прообраза
(2) совпадает с замкнутостью относительно взятия полного гомоморфного прообраза
(3) не имеет смысла
Класс языков, распознаваемых детерминированными автоматами с магазинной памятью
(1) очень важен для практических приложений
(2) не имеет значения для практических приложений
(3) игнорируется практическими приложениями
Протокол вывода в контекстно-свободной грамматике - это
(1) последовательность символовк
(2) последовательность правил
(3) ограничение определения приоритетов
Совокупность четырех составляющих, принадлежащих ленточному алфавиту, итерации ленточного алфавита и множеству состояний носит название
(1) аддитивная интерполяция
(2) конъюнктивная корреляция
(3) конфигурация
К видам порождающей грамматики относят
(1) неукорачивающую грамматику
(2) несовместно-контекстную грамматику
(3) грамматику свободных символов и пустых слов
Проблема бесконечности пересечения контекстно-свободных языков
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Некоторым детерминированным конечным автоматом можно задать
(1) каждый автоматный язык
(2) только один автоматный язык
(3) только определенный класс автоматных языков
Необходимые условия автоматности определяют, что формальный язык
(1) не является автоматным
(2) является автоматным
(3) является контекстным
Образы локальных языков при побуквенных гомоморфизмах являются
(1) автоматными языками
(2) пустыми множествами
(3) неопределенными множествами
Символы, обозначающие итерацию, конкатенацию и объединение языков, используются
(1) в автоматах
(2) в грамматиках
(3) в регулярных выражениях
Классы эквивалентности по взаимозаменяемости сами являются автоматными языками
(1) относительно автоматного языка
(2) по отношению к пустым словам
(3) относительно повторяющихся символов
Подкласс языков, для которых существует хотя бы одна однозначная грамматика, включает в себя
(1) все праволинейные языки
(2) все автоматные языки
(3) только определенный класс автоматных языков
Каждую контекстно-свободную грамматику можно
(1) проинтерполировать
(2) привести к нормальной форме Грейбах
(3) привести к упрощенной форме Коха
Явление "периодичности" в контекстно-свободных языках формализует
(1) теорема неоднозначности
(2) лемма о разрастании
(3) аксиома инъективности
Неотрицательные целые числа называют
(1) натуральными
(2) рациональными
(3) иррациональными
Наличие потенциально бесконечной памяти характерно для
(1) конечного автомата
(2) автомата с магазинной памятью
(3) конечного автомата и для автомата с магазинной памятью
Произвольный язык
(1) может быть контекстно-свободным
(2) не может быть контекстно-свободным
(3) не имеет смысла, как понятие
Автоматы с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами - это
(1) детерминированные автоматы с магазинной памятью
(2) аддитивные автоматы с магазинной памятью
(3) инъективные автоматы с магазинной памятью
Разные протоколы соответствуют
(1) разным левосторонним выводам
(2) одинаковым левосторонним выводам
(3) итерационным левосторонним выводам
Изображать машины Тьюринга в виде диаграмм
(1) можно
(2) нельзя
(3) не имеет практического смысла
Неукорачивающей является
(1) грамматика свободных символов
(2) грамматика пустых слов
(3) каждая контекстная грамматика
Проблема равенства контекстно-свободных языков
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Если в конечном автомате имеются несколько переходов с общим началом и общим концом, то такие переходы называются
(1) последовательными
(2) параллельными
(3) неординарными
Использование свойств замкнутости класса всех автоматных языков, как достаточных условий автоматности
(1) возможно
(2) невозможно
(3) не имеет практического применения
Наличие числового критерия для языков над однобуквенным алфавитом определяет
(1) автоматность языка
(2) гомоморфность языка
(3) контекстность языка
В качестве формализма, с помощью которого задаются классы однотипных лексем, регулярные выражения используются
(1) в автоматических генераторах лексических анализаторов
(2) интерпретаторах командной строки
(3) текстовых редакторах
Изоморфным автомату считается
(1) любой минимальный полный детерминированный конечный автомат
(2) последовательный полный детерминированный конечный автомат
(3) неполный детерминированный автомат
Деревья вывода - это
(1) некоторые упорядоченные деревья, вершины которых помечены символами принадлежности алфавиту
(2) ветвевидные структурные элементы, состоящие из пустых слов и отдельных символов
(3) ветвевидные элементы, определяющие последовательность символов алфавита
Полезными и достижимыми бывают
(1) символы
(2) ветки дерева вывода
(3) множества
Зависимость между длиной кроны дерева вывода и количеством вершин в самом длинном пути
(1) не определена
(2) существует и определяется формулами
(3) отсутствует
Конечное непустое множество символов - это
(1) пространство символов
(2) алфавит
(3) язык
В роли стека в автоматах с магазинной памятью используется
(1) память, хранящая текущее состояние
(2) бесконечная память
(3) как память, хранящая текущее состояние, так и бесконечная память
Задание гомоморфизма равенствами
(1) возможно
(2) невозможно
(3) не имеет смысла
Добавление в конец каждого слова языка специального символа применяется
(1) для получения полезного и естественного класса языков
(2) при формировании инверсного алфавита
(3) с целью уменьшения избыточности языка
Корень дерева вывода при префиксном обходе посещается
(1) в первую очередьв
(2) последним
(3) в середине данного цикла
Стрелкой на диаграмме, изображающей машину Тьюринга, обозначают
(1) состояние
(2) переход
(3) как переход, так и состояние
Некоторой контекстной грамматике
(1) эквивалентна каждая неукорачивающая грамматика
(2) эквивалентен только определенный класс неукорачивающих грамматик
(3) не ставится в соответствие ни одна неукорачивающая грамматика
Проблема пересечения контекстно-свободных языков
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Если слово является меткой некоторого успешного пути, то оно
(1) не допускается конечным автоматом
(2) допускается конечным автоматом
(3) игнорируется конечным автоматом
Пересечение автоматных языков дает в итоге
(1) контекстно-неординарный язык
(2) праволинейное множество
(3) также автоматный язык
С длинами слов обычно связывают
(1) условия непрерывности
(2) контекстность
(3) автоматность
Операция умножения по приоритету
(1) выше итерации
(2) ниже итерации
(3) подобна итерации
Алгоритм, позволяющий по произвольному детерминированному конечному автомату находить минимальный
(1) существует
(2) не определен
(3) не существует
Начальному символу отвечает
(1) корень дерева вывода
(2) верхняя ветка дерева
(3) главная ветка дерева вывода
Множества, определяющие, что контекстно-свободная грамматика эквивалентна исходной грамматике
(1) никогда не могут быть определены
(2) могут быть определены
(3) не существуют
Если длина кроны равна 32, то количество вершин в самом длинном пути равно
(1) 6
(2) 7
(3) 8
По определению, строка - это
(1) конечная последовательность элементов алфавита
(2) бесконечная последовательность элементов алфавита
(3) набор символов в строго определенном порядке
Структура данных, где в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов, носит название
(1) бесконечная память
(2) память, хранящая текущее состояние
(3) аддитивно-доступная память
Каждому символу можно поставить в соответствие
(1) конечный язык
(2) интерполяционный символ
(3) аддитивное слово
Маркером конца слова называют специальный символ, добавляемый
(1) в конец каждого слова
(2) в начало каждого слова
(3) в середину каждого слова
Протокол любого левостороннего вывода слова в грамматике имеет название
(1) левого подхода
(2) левой итерации
(3) левого разбора
Вычисление функций
(1) не свойственно машине Тьюринга
(2) присуще машине Тьюринга
(3) не имеет смысла в машине Тьюринга
Машину Тьюринга при наличии специальных условий можно назвать
(1) итерационно ограниченным автоматом
(2) аддитивно преобразованным автоматом
(3) линейно ограниченным автоматом
Алгоритм, позволяющий определить, является ли пустым множеством пересечение языков грамматик
(1) существует
(2) не может быть создан
(3) работает во всех случаях, даже самых сложных
Два конечных автомата называют эквивалентными, если
(1) они распознают один и тот же язык
(2) если они одинаковы
(3) если их можно объединить
Неавтоматность формального языка позволяет установить
(1) лемма об увеличении количества символов
(2) теорема автоматности
(3) лемма о разрастании
Составить автоматный язык можно
(1) имея связанные между собой гомоморфизм и автоматный язык
(2) при помощи набора символов и пустых слов
(3) с помощью гомоморфов и пустых слов
Некоторый язык над алфавитом задает
(1) множество целых чисел
(2) набор контекстных выражений
(3) каждое регулярное выражение над алфавитом
Полиномиальный алгоритм, позволяющий по произвольному конечному автомату находить минимальный автомат
(1) существует
(2) не существует
(3) неизвестно, существует или нет
Вершина дерева соответствует
(1) символу слова, на которое заменяется начальный символ на первом шаге вывода
(2) символу слова, который идентичен начальному
(3) набору символов, с которых начинается построение алфавита
Если контекстно-свободный язык не содержит пустого слова, то
(1) он может порождаться некоторой грамматикой
(2) он не может порождаться грамматикой
(3) он не определяется ни одной из грамматик
Эквивалентной по отношению к линейной грамматике в нормальной форме считается
(1) нелинейно выраженная грамматика
(2) любая линейная грамматика
(3) грамматика с множеством пустых слов
Произведение операции пересечения языков, заданных над одним и тем же алфавитом
(1) возможно
(2) невозможно
(3) не имеет практического применения
Порядок записи содержимого стека
(1) имеет значение
(2) не имеет значения
(3) не проверяется
Наличие критериев контекстной свободности
(1) не доказано
(2) вполне реально
(3) не доказано, так как не имеет практического смысла
Если автомат с магазинной памятью имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны, то его называют
(1) итерационным
(2) инъективным
(3) детерминированным
Нисходящим разбором принято называть
(1) процесс нахождения левого разбора слова
(2) процесс нахождения правого разбора слова
(3) разделение символов алфавита по группам
Вычисление частичных функций
(1) не свойственно машине Тьюринга
(2) присуще машине Тьюринга
(3) не имеет смысла в машине Тьюринга
Класс языков, порождаемых неукорачивающими грамматиками, замкнут относительно
(1) пересечения
(2) дополнения
(3) объединения
Определить однозначность грамматики по произвольной контекстно-свободной грамматике
(1) невозможно
(2) возможно
(3) возможно только в несложных случаях
Каждый конечный язык является
(1) автоматным
(2) недетерминированным
(3) однородным
Относительно итерации, конкатенации и объединения класс автономных языков
(1) не определен
(2) замкнут
(3) не образуется
С помощью конечного автомата можно
(1) определить совместимость языково
(2) задать исходный язык
(3) провести интерполяцию символов
Метка пути обобщенного конечного автомата - это
(1) обобщение регулярных выражений на переходах данного пути
(2) произведение регулярных выражений на переходах данного пути
(3) сумма регулярных выражений на переходах данного пути
Кроной называют
(1) набор символов, находящихся в начальных частях веток
(2) слово, записанное в вершинах, помеченных символами из алфавита
(3) совокупность меток, определяющих порядок распознавания символов в дереве
Эквивалентной некоторой грамматике в нормальной форме Грейбах является
(1) любая контекстно-свободная грамматика
(2) неоднозначная контекстно-свободная грамматика
(3) инъективная грамматика
Чтобы быть порождаемым линейной грамматикой в нормальной форме линейный язык
(1) должен содержать пустое слово
(2) не должен содержать пустых слов
(3) должен сам являться по своей сути пустым словом
Обращением или зеркальным образом называют
(1) слово, в котором символы, составляющие слово, идут в обратном порядке
(2) множество слов, составляющих логическую последовательность
(3) алфавит с символами в обратном порядке
При определении автомата магазинной памяти используют
(1) множество состояний
(2) заключительные состояния
(3) допускающие состояния
Определение критериев контекстной свободности
(1) невозможно
(2) возможно
(3) не имеет применения
Каждый автоматный язык является
(1) детерминированным контекстно-свободным языком
(2) детерминированным контекстно-ограниченным языком
(3) детерминированным контекстно-обусловленным языком
Вычислительный процесс автомата с магазинной памятью по своей сути является
(1) полным итерационным инъективным множеством
(2) пустым множеством
(3) последовательностью конфигураций
Допускающее и отвергающее состояниет
(1) не характерны для машины Тьюринга
(2) являются состояниями машины Тьюринга
(3) не имеют смысла для машины Тьюринга
Пересечение выражается через
(1) объединение и дополнение
(2) обобщение и дополнение
(3) обобщение и объединение
Если постовская система соответствия имеет решение, то грамматика является
(1) неоднозначной
(2) однозначной
(3) аддитивной
"Мгновенное описание" конечного автомата описывается
(1) конфигурацией
(2) символьной дислокацией
(3) линейной интерполяцией
Конечным автоматом с одним начальным и одним заключительным состоянием можно задать
(1) любой исходный автоматный язык
(2) только контекстный язык
(3) только ординарно-контекстный язык
Понятие "побуквенный" относится к
(1) начальному автомату
(2) конечному автомату
(3) гомоморфизму
Слово допускается обобщенным конечным автоматом, если оно
(1) пустое
(2) принадлежит языку, задаваемому меткой некоторого успешного пути
(3) имеет соответствие с любым контекстным языком
Непустое множество с ассоциативной бинарной операцией умножения называется
(1) подгруппа
(2) полугруппа
(3) полуподгруппа
В контекстно-свободной грамматике для каждого выводимого слова существует
(1) правосторонний вывод
(2) левосторонний вывод
(3) как правосторонний, так и левосторонний вывод
Метод индукции для приведения грамматики в нормальную форму Грейбах
(1) используется
(2) не применим
(3) не определен, как метод
Представление линейного языка в виде объединения двух линейных языков
(1) возможно
(2) невозможно
(3) не имеет смысла
Элементы вспомогательного алфавита называются
(1) нетерминалами
(2) терминальными символами
(3) переменными символами
Изображение автоматов с магазинной памятью посредство диаграмм состояний
(1) возможно
(2) невозможно
(3) не имеет практического смысла
Если два языка порождены разными грамматиками, то сформировать определенный гомоморфизм
(1) невозможно
(2) возможно по определенным правилам
(3) не нужно - практически не применимо
Индукцией по сумме избытков всех переходов доказывается
(1) эквивалентность автоматов с магазинной памятью
(2) эквипотенциальность автоматов с магазинной памятью
(3) аддитивность автоматов с магазинной памятью
Сентенциальная форма грамматики по своей сути является
(1) алфавитом
(2) языком
(3) словом
Рекурсивным является язык над алфавитом, если детерминированная машина Тьюринга
(1) существует
(2) не существует
(3) не определена
Для определения бесконечности языка
(1) существует определенный алгоритм
(2) невозможно составить алгоритм
(3) не имеет практического смысла применять алгоритмы
Линейную грамматику можно получить путем
(1) интерполирования аддитивных символов
(2) отождествления инъективной грамматики
(3) "раскрытием" определенных вспомогательных символов
Праволинейным является
(1) любой автоматный язык
(2) только однородный автоматный языки
(3) неоднородный автоматный язык
Относительно дополнения и пересечения класс автоматных языков
(1) не определен
(2) обобщен
(3) замкнут
Понятие "локальный" относится к
(1) гомоморфизму
(2) языку
(3) символу
Замена в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв приведет к
(1) преобразованию конечного автомата в обобщенный конечный автомат
(2) замене автомата на более простой
(3) увеличению символов алфавита вдвое
Моноид - это
(1) символ, обозначающий единицу во всех алфавитах
(2) набор символов, не больших единицы
(3) полугруппа с единицей, принадлежащей множеству
Неоднозначной называют контекстно-свободную грамматику, если есть слово, имеющее
(1) два левосторонних вывода
(2) три левосторонних вывода
(3) один левосторонний вывод
Укажите верное утверждение:
(1) если контекстно-свободный язык не содержит пустого слова, то он игнорируется некоторой грамматикой
(2) если контекстно-свободный язык не содержит пустого слова, то он порождается некоторой грамматикой
(3) если контекстно-свободный язык содержит пустое слово, то он порождается некоторой грамматикой
Составление контекстно-свободного языка, как произведения контекстно-свободных языков
(1) возможно
(2) невозможно
(3) не имеет практического смысла
Каждая линейная грамматика является
(1) контекстной
(2) контекстно-свободной
(3) свободной
Множество всех слов, допускаемых автоматом с магазинной памятью, формирует
(1) алфавит
(2) язык
(3) корреляцию символов
Какое из утверждений является неверным?
(1) к свойствам замкнутости класса контекстно-свободных языков относят замкнутость относительно деления
(2) к свойствам замкнутости класса контекстно-свободных языков не относят замкнутость относительно взятия гомоморфного образа и полного гомоморфного прообраза
(3) к свойствам замкнутости класса контекстно-свободных языков относят замкнутость относительно полного гомоморфного прообраза
Детерминированным контекстно-свободным языком является
(1) дополнение детерминированного контекстно-свободного языка
(2) обобщение детерминированного контекстно-свободного языка
(3) итерация контекстно-свободного языка
Обращенную последовательность правил, примененных в выводе называют
(1) левосторонним выводом
(2) правосторонним выводом
(3) усредненным выводом
Если существует детерминированная машина Тьюринга, допускающая язык, то он называется
(1) полуразрешимым
(2) перечислимым
(3) рекурсивно перечислимым
Если грамматика не содержит "рекурсивные" нетерминальные символы, то
(1) язык является бесконечным
(2) язык является конечным
(3) невозможно определить конечность языка
Дополнение языка является бесконечным тогда и только тогда, когда постовская система соответствия
(1) имеет решение
(2) не имеет решения
(3) не определена
Каждый автоматный язык
(1) распознается полным детерминированным конечным автоматом
(2) игнорируется полным детерминированным конечным автоматом
(3) имеет в себе полный детерминированый конечный автомат
Через объединение и дополнение выражается
(1) итерация
(2) конкатенация
(3) пересечение
Каждый локальный язык является
(1) программным
(2) контекстным
(3) автоматным
Минимум звездных высот регулярных выражений, задающих язык, называется
(1) звездностью
(2) звездным порядком
(3) звездной высотой
Синтаксический моноид конечен в том случае, когда
(1) язык является совместным
(2) язык является автоматным
(3) определена область его значений
Однозначной называют контекстно-свободную грамматику, если отсутствует слово, имеющее
(1) два левосторонних вывода
(2) два правосторонних вывода
(3) два или более левосторонних вывода
Определите неверное утверждение:
(1) каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского
(2) квадратичная грамматика является контекстно-свободной
(3) грамматики не могут быть эквивалентны
Представление линейного языка в виде объединения двух линейных языков
(1) возможно
(2) невозможно
(3) не имеет смысла
К способам конечного описания формального языка относят
(1) порождающие грамматики
(2) автоматы
(3) регулярные выражения
Вид автоматов, соответствующих контекстно-свободным грамматикам называется
(1) детерминанты
(2) конечные автоматы
(3) автоматы с магазинной памятью
Замкнутость относительно взятия гомоморфного образа
(1) не является свойством замкнутости класса контекстно-свободных языков
(2) является свойством замкнутости класса контекстно-свободных языков
(3) не имеет смысла по отношению к классу контекстно-свободных языков
Теорема о детерминизации для конечных автоматов и аналогичная теорема для автоматов с магазинной памятью
(1) совпадают
(2) отличаются
(3) абсолютно идентичны друг другу
Синтаксический разбор - это
(1) система методов, направленных на разделение символов по группам
(2) процесс нахождения дерева вывода слова
(3) применение итерации ко всем словам алфавита
В машину Тьюринга включают
(1) множество переходов
(2) множество начальных состояний
(3) множество конечных состояний
Проблема эквивалентности конечных автоматов
(1) разрешима и очень проста
(2) разрешима, но сложна
(3) неразрешима
С помощью контекстно-свободной грамматики и автоматов с магазинной памятью
(1) можно представить язык
(2) невозможно представить язык
(3) не имеет смысла представлять язык
Грамматики и автоматы
(1) наиболее распространенные способы конечного задания формального языка
(2) нераспространенные способы конечного задания формального языка
(3) не используют для конечного задания формального языка
Использование специальных средств, позволяющих выяснять, является ли некоторый формальный язык автоматным
(1) необходимо для практического применения теории конечных автоматов
(2) не используется для практического применения теории конечных автоматов
(3) является специфическим и используется редко
Относительно взятия полного гомоморфного прообраза
(1) производится определение пустых слов языка
(2) находятся символьные несоответствия
(3) класс всех автоматных языков замкнут
С помощью регулярных выражений можно производить
(1) конечное описание формального языка
(2) проверку на наличие пустых слов
(3) проверку контекстности языка
Соответствующие классы эквивалентности слов позволяют
(1) найти все пустые слова
(2) упростить работу с любым алфавитом
(3) построить минимальный детерминированный конечный автомат для заданного языка
Программные средства статического анализа программ основаны на
(1) автоматах
(2) грамматиках
(3) контекстно-свободных языках
Каждая контекстно-свободная грамматика по отношению к грамматике в нормальной форме Хомского является
(1) неопределенной
(2) неоднозначной
(3) эквивалентной
Определение замкнутости класса контекстно-свободных языков относительно дополнения и пересечения
(1) возможно
(2) невозможно
(3) не имеет смысла
Все грамматики
(1) могут принадлежать к разным классам
(2) принадлежат только одному классу
(3) не классифицируются
Конечные автоматы
(1) отличаются от автоматов с магазинной памятью
(2) являются автоматами с магазинной памятью
(3) являются неоднородно распределяемыми аддитивными автоматами
Замкнутость относительно взятия полного гомоморфного прообраза
(1) отличается от замкнутости относительно деления
(2) совпадает с замкнутостью относительно деления
(3) не имеет смысла
Формирование нового класса языков при использовании в автоматах с магазинной памятью теоремы о детерминизации
(1) является возможным
(2) не производится
(3) не имеет смысла
Протоколом левостороннего вывода в контекстно свободной грамматике принято называть
(1) последовательность правил, примененных в этом выводе
(2) свойства обмена символами между языками
(3) зависимость количества символов алфавита от его избыточности
Конфигурация машины Тьюринга состоит из
(1) четырех составляющих
(2) восьми составляющих
(3) шестнадцати составляющих
Термин "неукорачивающая" относят к
(1) порождающей грамматике
(2) контекстно-несвободной интерполяции
(3) итерации
Проблемы пустоты и бесконечности пересечения контекстно-свободных языков
(1) не сформулированы в общем виде
(2) не имеют решения
(3) всегда разрешимы
Конечные автоматы специального вида
(1) читают на каждом такте один символ и имеют одно начальное состояние
(2) читают на каждом такте ровно один символ, но имеют два начальных состояния
(3) читают на каждом такте два символа и имеют два начальных состояния
Применение достаточных и необходимых условий автоматности определяет, является ли некоторый формальный язык
(1) автоматным
(2) контекстным
(3) независимым
Критерием автоматности можно считать
(1) получение количества слов в языке
(2) наличие гомоморфных периодичных символов
(3) наличие или отсутствие пустого слова
Символ "звездочка" используется для обозначения
(1) итерации
(2) конкатенации
(3) объединение языков
Множество правых контекстов слова относительно языка
(1) бесконечно
(2) счетное
(3) не определено
К подклассу языков, для которых существует хотя бы одна однозначная грамматика, относят
(1) детерминированные автоматы
(2) праволинейные языки
(3) неопределенно-инъективные языки
Символ грамматики может быть
(1) полезным
(2) атрофированным
(3) инъективно-неопределенным
Класс линейных языков
(1) имеет значение только теоретически
(2) имеет значение и в теории, и на практике
(3) не играет значительной роли ни в теории, ни на практике
Натуральные числа - это
(1) числа, которые подлежат счету
(2) неотрицательные целые числа
(3) множество всех целых чисел
В автомате с магазинной памятью присутствует
(1) ограниченная память, хранящая текущее состояние
(2) потенциально бесконечная память
(3) инъективная память
Контекстно-свободный язык
(1) может образовываться из произвольного языка
(2) не может быть образован из произвольного языка
(3) не связан с произвольным языком
Выбор тактов детерминированными автоматами с магазинной памятью
(1) не осуществляется
(2) осуществляется
(3) не имеет практического назначения
НПротокол левостороннего вывода в контекстно-свободной грамматике является описанием соответствующего дерева вывода
(1) в порядке суффиксного обхода
(2) в порядке префиксного обхода
(3) посредством усреднения между суффиксным и префиксным обходами
Недетерминированная машина Тьюринга
(1) существует
(2) не существует
(3) не определена
Определите верное утверждение:
(1) каждая контекстная грамматика является неукорачивающей
(2) любая контекстная грамматика не может является неукорачивающей
(3) контекстная грамматика не определяется понятием неукорачиваемости
Проблема автоматности контекстно-свободного языка
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Параллельными называют переходы
(1) с общим началом и концом
(2) с общим началом, но разными концами
(3) с разными началами и концами
Свойства замкнутости класса всех автоматных языков используют
(1) для определения наличия пустых слов
(2) как достаточные условия автоматности
(3) как своего рода фильтр ненужных слов языка
Критерий автоматности для языков над однобуквенным алфавитом бывает:
(1) периодичным
(2) числовым
(3) итерационным
В текстовых редакторах и интерпретаторах командной строки применяются
(1) автоматы
(2) неотрицательные целые числа
(3) регулярные выражения
Слово различает состояния полного детерминированного конечного автомата, если
(1) одно из состояний заключительное, а другое таковым не является
(2) оба состояния заключительные
(3) оба состояния не являются заключительными
Понятие однозначности контекстно-свободной грамматики
(1) неразрывно связано с понятием дерева вывода
(2) стоит отдельно от дерева вывода
(3) совпадает с понятием дерева вывода
Понятие "порождающий" касается
(1) детерминанта
(2) автомата
(3) символа
Определение длины кроны дерева вывода, если известно только количество вершин в самом длинном пути
(1) невозможно
(2) всегда возможно
(3) не имеет практического смысла
Элементы алфавита называются
(1) символами
(2) буквами
(3) знаками
Функцию магазина в автоматах с магазинной памятью выполняет
(1) память, хранящая текущее состояние
(2) бесконечная память
(3) как бесконечная память, так и память текущего состояния
С помощью равенств
(1) можно задать гомоморфизми
(2) невозможно задать гомоморфизм
(3) не имеет смысла задавать гомоморфизм
Добавление символов к словам для получения нового класса языков
(1) не используется из-за значительной трудоемкости
(2) используется всегда
(3) не имеет практического применения
Префиксный обход первого непосредственного потомка корня выполняется
(1) после обхода корня
(2) непосредственно во время обхода корня
(3) перед осмотром корня
Кружок на диаграмме, изображающей машину Тьюринга, обозначает
(1) переход
(2) состояние
(3) заключительное состояние
Любая неукорачивающая грамматика связана с некоторой контекстной грамматикой понятием
(1) неопределенности
(2) эквивалентности
(3) эквипотенциальности
Проблема контекстной свободности дополнения контекстно-свободного языка и пересечения контекстно-свободных языков
(1) не сформулирована
(2) не имеет решения
(3) всегда разрешима
Язык, состоящий из меток всех успешных путей, является
(1) распознаваемым конечным автоматом
(2) нераспознаваемым конечным автоматом
(3) игнорируемым конечным автоматом
Автоматный язык можно получить
(1) при пересечении неоднородных языков
(2) при наложении друг на друга двух контекстных подмножеств
(3) при пересечении автоматных языков
Для произвольного алфавита необходимое условие автоматности
(1) не является обязательным
(2) может быть связано с длинами слов
(3) отсутствует
Приоритет сложения
(1) выше приоритета итерации
(2) ниже приоритета итерации
(3) подобен приоритету итерации
Минимальность детерминированного автомата определяется
(1) количеством пустых слов
(2) количеством состояний
(3) количеством символови
Деревья разбора - это
(1) деревья вывода
(2) структурные элементы контекстного языка
(3) программы, отвечающие за просмотр непустых множеств
Для определения такого множества, что в контекстно-свободной грамматике не присутствуют бесполезные символы, необходимо удалить
(1) все непорождающие символы
(2) каждое правило, содержащее непорождающие символы
(3) как непорождающие символы, так и содержащие их правила
Количество вершин в самом длинном пути, равное пяти соответствует длине кроны
(1) 8
(2) 32
(3) 64
Слово, не содержащее ни одного символа, называется
(1) пустым
(2) нулевым
(3) неотождествленным
В определенный момент обработки
(1) доступен только один элемент бесконечной памяти
(2) доступна пара элементов бесконечной памяти
(3) доступны все элементы бесконечной памяти
Конечный язык можно поставить в соответствие
(1) только пустому символу
(2) каждому символу
(3) инъективному символу
Специальный символ, добавляемый в конец каждого слова, называется
(1) стимер
(2) маркер
(3) приоритет
Левый разбор по своей сути является
(1) символом
(2) алфавитом
(3) протоколом
Способность машины Тьюринга вычислять функции
(1) присутствует
(2) не определена
(3) отсутствует
Машина Тьюринга
(1) может быть линейно ограниченным автоматом только при определенных условиях
(2) не может быть линейно ограниченным автоматом
(3) без всяких условий по умолчанию всегда является линейно ограниченным автоматом
Если постовская система соответствия имеет хотя бы одно решение, то
(1) она имеет бесконечно много решений
(2) она имеет только это решение
(3) она не является определенной
Если существует конечный автомат, распознающий язык, то этот язык называется
(1) конечным
(2) автоматным
(3) конечно-автоматным
Лемма о разрастании дает
(1) критерий автоматности
(2) дает необходимое условие, а не критерий автоматности
(3) дает и необходимое условие, и критерий автоматности
Наличие гомоморфа и автоматного языка при определенных условиях позволяет
(1) определить количество пустых слов в языке
(2) составить автоматный язык
(3) произвести проверку наличия несоответствий в языке
Язык называется регулярным, если
(1) он задается некоторым регулярным выражением
(2) в нем регулярно встречаются подобные фразы
(3) осуществляется регулярная проверка наличия пустых слов
Быстрый алгоритм, позволяющий по произвольному конечному автомату находить минимальный автомат, приобрел название
(1) макросистемный
(2) полиномиальный
(3) мультиавтоматный
Непосредственные "потомки" корня
(1) располагаются случайным образом в структуре дерева
(2) упорядочены согласно порядку их меток в слове
(3) упорядочены по убыванию или возрастанию
Контекстно-свободный язык может порождаться некоторой грамматикой, если он
(1) не содержит пустого слова
(2) содержит пустое слово
(3) является пустым словом
Отношение любой линейной грамматики к линейной грамматике в нормальной форме определяется ее
(1) эквивалентностью
(2) эквипотенциальностью
(3) неоднозначностью символов
Множеством можно назвать
(1) любой язык
(2) только язык высокого уровня
(3) только язык символов, объединенных общими признаками
Вершина стека находится
(1) в начале слова
(2) в конце слова
(3) справа
Существуют ли критерии контекстной свободности?
(1) да
(2) нет
(3) неизвестно
Детерминированный автомат с магазинной памятью имеет
(1) одно начальное состояние
(2) пару начальных состояний
(3) бесконечное множество начальных состояний
По своей сути нисходящий разбор является
(1) итерационным шагом
(2) аддитивным преобразованием
(3) процессом нахождения левого разбора слова
Способность машины Тьюринга вычислять частичные функции
(1) присутствует
(2) не определена
(3) отсутствует
Относительно пересечения, дополнения и объединения класс контекстных языков является
(1) неопределенным
(2) необозначенным
(3) замкнутым
По произвольной контекстно-свободной грамматике
(1) нельзя определить однозначность грамматики
(2) определяют однозначность грамматики
(3) определяют однозначность грамматики только в самых сложных случаях
Конечный преобразователь является
(1) линейной интерпретацией любого языка
(2) заменителем символов для любого языка
(3) естественным обобщением конечного автомата
Итерация, конкатенация и объединение определяют
(1) замкнутость класса автоматных языков
(2) непрерывность класса автоматных языков
(3) контекстность и корректность класса автоматных языков
Применение конечного автомата позволяет
(1) найти связь между несовместимыми символами
(2) задать исходный язык
(3) определить, является ли язык контекстным
Произведение регулярных выражений на переходах пути имеет название
(1) карта пути
(2) метка пути
(3) размер пути
Множество двусторонних контекстов
(1) определено
(2) не определено
(3) не имеет смысла
Крона, по своей сути, является
(1) словом
(2) значением
(3) символом
В грамматике в нормальной форме Грейбах существуют правила
(1) трех видов
(2) четырех видов
(3) шести видов
Содержание в линейном языке пустого слова приведет к
(1) порождению этого языка некоторой линейной грамматикой в нормальной форме
(2) невозможности порождения этого языка некоторой линейной грамматикой в нормальной форме
(3) невозможности использования этого языка в дальнейшеми
Определение гомоморфизма своими значениями на однобуквенных словах
(1) однозначно
(2) отсутствует
(3) многозначно
Количество составляющих автомата с магазинной памятью равно
(1) 6
(2) 12
(3) 18
Имеет ли смысл определения критериев контекстной свободности?
(1) нет
(2) да, но чисто с теоретической точки зрения
(3) нет, так как определение контекстно-свободного языка противоречит этому
Детерминированным контекстно-свободным языком называют
(1) любой язык
(2) любой автоматный язык
(3) любое непустое множество
Одним тактом работы автомата с магазинной памятью получается
(1) любая из конфигураций
(2) любая конфигурация, кроме первой
(3) любая конфигурация, исключая последнюю
Детерминированная машина Тьюринга с выделенным состоянием
(1) может разрешать язык
(2) не может разрешать язык
(3) не работает с языками
Через объединение и дополнение выражают
(1) обобщение
(2) итерацию
(3) пересечение
Если постовская система соответствия не имеет решения, то грамматика
(1) является неоднозначной
(2) не является неоднозначной
(3) является аддитивной
Полный детерминированный конечный автомат не должен содержать переходов с метками длины
(1) больше единицы
(2) меньше двух
(3) меньше трех
Одним из видов гомоморфизма является
(1) гомоморфизм с коррекцией
(2) побуквенный гомоморфизм
(3) гомоморфизм с итерациями
Каждый конечный автомат можно преобразовать в
(1) набор команд и чисел
(2) обобщенный конечный автомат, допускающий те же слова
(3) обобщенный конечный автомат, игнорирующий пустые слова
Полугруппа представляет собой
(1) непустое множество
(2) пустое множество
(3) иррациональное множество
В контекстно-свободной грамматике левосторонний вывод существует
(1) только для пустых слов
(2) для детерминированных слов
(3) для всех слов
Приведение шагов индукции для определения грамматики в нормальную форму Грейбах
(1) используется
(2) не применяется
(3) не имеет смысла, как метод
Итерация контекстно-свободного языка
(1) не является контекстно-свободным языком
(2) является контекстно-свободным языком
(3) не имеет практического смысла
Если две грамматики порождают один и тот же язык, то они называются
(1) тождественными
(2) эквивалентными
(3) эквипотенциальными
Для изображения автоматов с магазинной памятью используют
(1) пустые множества
(2) диаграммы состояний
(3) как пустые множества, так и диаграммы состояний
Если два языка порождены одинаковыми грамматиками, то формировать любые гомоморфизмы
(1) не имеет смысла
(2) возможно
(3) невозможно
При помощи метода индукции по сумме избытков всех переходов можно определить
(1) независимость автоматов с магазинной памятью
(2) перенаправленность автоматов с магазинной памятью
(3) эквивалентность автоматов с магазинной памятью
Сентенциальная форма
(1) может быть присуща грамматике
(2) несвойственна грамматике
(3) не связана с понятием грамматики
Разрешенным является язык над алфавитом, если детерминированная машина Тьюринга
(1) существует
(2) не существует
(3) не определена
Чтобы определить, является ли язык бесконечным
(1) не нужно удалять бесполезные символы
(2) нужно удалить половину бесполезных символов
(3) нужно полностью избавиться от бесполезных символов
Получение линейной грамматики посредством "раскрытия" определенных вспомогательных символов
(1) невозможно
(2) возможно
(3) не применяется из-за сложности вычислений
Каждый праволинейный язык является
(1) контекстно-неоднородным
(2) автоматным
(3) линейно-контекстным
Дополнение и пресечение определяют
(1) замкнутость класса автоматных языков
(2) контекстность класса автоматных языков
(3) однородность и ординарность класса автоматных языков
Одним из видов языков является
(1) локальный язык
(2) глобальный язык
(3) язык символов с переменным значением
Если к обобщенному конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов
(1) не изменится
(2) увеличится вдвое
(3) уменьшится вдвое
Моноид по своей сути
(1) полугруппа
(2) подгруппа
(3) детерминационный элемент
Неопределенная грамматика - это
(1) контекстно-свободная грамматика, имеющая только пустые слова
(2) контекстно-свободная грамматика, не определяющая строгой зависимости между символами
(3) контекстно-свободная грамматика, имеющая слово с двумя левосторонними выводами
Укажите верное утверждение:
(1) проведение преобразований грамматики так, что порождаемый ею язык остается неизменным невозможно
(2) проведение преобразований грамматики так, что порождаемый ею язык остается неизменным возможно
(3) проведение преобразований грамматики так, что порождаемый ею язык остается неизменным не имеет смысла
Пресечение контекстно-свободных языков
(1) дает контекстно-свободный язык
(2) не дает в итоге контекстно-свободный язык
(3) не имеет смысла вообще
Каждая праволинейная грамматика является
(1) контекстной
(2) контекстно-свободной
(3) линейной
Если автоматы с магазинной памятью распознают один и тот же язык, то они
(1) эквивалентны
(2) аддитивны
(3) несоответственны
Определите верное утверждение:
(1) каждому символу можно поставить в соответствие конечный язык
(2) имея два языка, порожденных разными грамматиками, мы не сможем сформировать гомоморфизм
(3) к свойствам замкнутости класса контекстно-свободных языков не относят замкнутость относительно деления
Дополнение детерминированного контекстно-свободного языка является
(1) детерминированым контекстно-свободным языком
(2) пустым множеством
(3) символом
Разным правосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют
(1) одинаковые протоколы
(2) разные протоколы
(3) как одинаковые, так и разные протоколы
Каждый разрешимый язык является
(1) конъюнктивным
(2) инъективным
(3) перечислимым
По наличию "рекурсивных" нетерминальных символов
(1) невозможно определить конечность языка
(2) определяют конечность языка
(3) не имеет смысла определять конечность языка из-за нерациональности
Пересечение языков является непустым тогда и только тогда, когда постовская система соответствия
(1) имеет решение
(2) не имеет решения
(3) не определена
Праволинейный язык порождается некоторой праволинейной грамматикой в нормальной форме без эпсилон-правил, если
(1) не содержит ни одного пустого слова
(2) является строго контекстным
(3) имеет пустые слова
Построив по двум конечным автоматам с однобуквенными переходами новый конечный автомат можно доказать
(1) автоматность пересечения двух автоматных языков
(2) контекстность пересечения двух автоматных языков
(3) автоматность пересечения двух контекстных языков
Множество может быть
(1) заключительно периодическим
(2) незавершенным
(3) пустым
Звездная высота - это
(1) минимум звездных высот регулярных выражений, задающих язык
(2) максимум звездных высот регулярных выражений, задающих язык
(3) усредненное значение звездных высот регулярных выражений, задающих язык
Речь идет о конечном синтаксическом моноиде только тогда, когда
(1) в языке нет пустых слов
(2) язык является автоматным
(3) множество пустых чисел счетное
Существенно неоднозначным
(1) является любой праволинейный язык
(2) не является ни один праволинейный язык
(3) является только автомат и грамматика
Грамматика в нормальной бинарной форме - это
(1) грамматика в нормальной форме Грейбах
(2) грамматика в нормальной форме Хомского
(3) квадратичная грамматика
Итерация контекстно-свободного языка
(1) не является контекстно-свободным языком
(2) является контекстно-свободным языком
(3) не имеет практического смысла