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

Упражнение 1:

Номер 1

Наиболее удобным и компактным способом конечного описания формального языка являются

Ответ:

(1) грамматики

(2) автоматы

(3) регулярные выражения

Номер 2

Регулярные выражения представляют собой

Ответ:

(1) наиболее удобный и компактный способ описания формального языка

(2) наиболее трудоемкий способ описания формального языка

(3) наиболее неудобный и неудачный способ описания формального языка

Номер 3

С помощью регулярных выражений можно производить

Ответ:

(1) конечное описание формального языка

(2) проверку на наличие пустых слов

(3) проверку контекстности языка

Упражнение 2:

Номер 1

В регулярных выражениях используются символы, обозначающие

Ответ:

(1) итерацию

(2) конкатенацию

(3) объединение языков

Номер 2

Символы, обозначающие итерацию, конкатенацию и объединение языков, используются

Ответ:

(1) в автоматах

(2) в грамматиках

(3) в регулярных выражениях

Номер 3

Символ "звездочка" используется для обозначения

Ответ:

(1) итерации

(2) конкатенации

(3) объединение языков

Упражнение 3:

Номер 1

Регулярные выражения применяются в

Ответ:

(1) текстовых редакторах

(2) интерпретаторах командной строки

(3) программных средствах обработки трехмерной графики

Номер 2

В качестве формализма, с помощью которого задаются классы однотипных лексем,  регулярные выражения используются

Ответ:

(1) в автоматических генераторах лексических анализаторов

(2) интерпретаторах командной строки

(3) текстовых редакторах

Номер 3

В текстовых редакторах и интерпретаторах командной строки применяются

Ответ:

(1) автоматы

(2) неотрицательные целые числа

(3) регулярные выражения

Упражнение 4:

Номер 1

Операция итерации имеет приоритет

Ответ:

(1) выше, чем умножение

(2) ниже, чем умножение

(3) такой же, как и у умножения

Номер 2

Операция умножения по приоритету

Ответ:

(1) выше итерации

(2) ниже итерации

(3) подобна итерации

Номер 3

Приоритет сложения

Ответ:

(1) выше приоритета итерации

(2) ниже приоритета итерации

(3) подобен приоритету итерации

Упражнение 5:

Номер 1

Каждое регулярное выражение над алфавитом задает

Ответ:

(1) некоторый язык над алфавитом

(2) некоторое целое подмножество над алфавитом

(3) определенную последовательность натуральных чисел над алфавитом

Номер 2

Некоторый язык над алфавитом задает

Ответ:

(1) множество целых чисел

(2) набор контекстных выражений

(3) каждое регулярное выражение над алфавитом

Номер 3

Язык называется регулярным, если

Ответ:

(1) он задается некоторым регулярным выражением

(2) в нем регулярно встречаются подобные фразы

(3) осуществляется регулярная проверка наличия пустых слов

Упражнение 6:

Номер 1

Обобщенным конечным автоматом можно назвать

Ответ:

(1) аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями

(2) конечный автомат, использующий контекстные выражения

(3) автомат, реализующий проверку наличия пустых слов в языке

Номер 2

Метка пути обобщенного конечного автомата - это

Ответ:

(1) обобщение регулярных выражений на переходах данного пути

(2) произведение регулярных выражений на переходах данного пути

(3) сумма регулярных выражений на переходах данного пути

Номер 3

Произведение регулярных выражений на переходах пути имеет название

Ответ:

(1) карта пути

(2) метка пути

(3) размер пути

Упражнение 7:

Номер 1

Если слово принадлежит языку, задаваемому меткой некоторого успешного пути, то оно

Ответ:

(1) допускается обобщенным конечным автоматом

(2) игнорируется обобщенным конечным автоматом

(3) не учитывается при составлении алфавита

Номер 2

Слово допускается обобщенным конечным автоматом, если оно

Ответ:

(1) пустое

(2) принадлежит языку, задаваемому меткой некоторого успешного пути

(3) имеет соответствие с любым контекстным языком

Номер 3

Каждый конечный автомат можно преобразовать в

Ответ:

(1) набор команд и чисел

(2) обобщенный конечный автомат, допускающий те же слова

(3) обобщенный конечный автомат, игнорирующий пустые слова

Упражнение 8:

Номер 1

Преобразовать конечный автомат в обобщенный конечный автомат можно

Ответ:

(1) заменив в метках переходов пустое слово на 1, а каждое непустое слово - на сумму его букв

(2) заменив в метках переходов пустое слово на 0, а каждое непустое слово - на произведение его букв

(3) заменив в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв

Номер 2

Замена в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв приведет к

Ответ:

(1) преобразованию конечного автомата в обобщенный конечный автомат

(2) замене автомата на более простой

(3) увеличению символов алфавита вдвое

Номер 3

Если к обобщенному конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов

Ответ:

(1) не изменится

(2) увеличится вдвое

(3) уменьшится вдвое

Упражнение 9:

Номер 1

Язык является регулярным тогда и только тогда, когда он является

Ответ:

(1) независимым

(2) неоднородным

(3) автоматным

Номер 2

Минимум звездных высот регулярных выражений, задающих язык, называется

Ответ:

(1) звездностью

(2) звездным порядком

(3) звездной высотой

Номер 3

Звездная высота - это

Ответ:

(1) минимум звездных высот регулярных выражений, задающих язык

(2) максимум звездных высот регулярных выражений, задающих язык

(3) усредненное значение звездных высот регулярных выражений, задающих язык

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