Главная / Математическая теория формальных языков

Математическая теория формальных языков - ответы на тесты Интуит

Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.

Список вопросов:

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