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

Упражнение 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) праволинейным

(2) контекстным

(3) корректно-линейным

Номер 2

Праволинейным является

Ответ:

(1) любой автоматный язык

(2) только однородный автоматный языки

(3) неоднородный автоматный язык

Номер 3

Каждый праволинейный язык является

Ответ:

(1) контекстно-неоднородным

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

(3) линейно-контекстным

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

Номер 1

Полным детерминированным конечным автоматом

Ответ:

(1) распознается каждый автоматный язык

(2) не распознаются автоматные языки

(3) не имеет смысла производить распознавание автоматного языка

Номер 2

Каждый автоматный язык

Ответ:

(1) распознается полным детерминированным конечным автоматом

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

(3) имеет в себе полный детерминированый конечный автомат

Номер 3

Праволинейный язык порождается некоторой праволинейной грамматикой в нормальной форме без эпсилон-правил, если

Ответ:

(1) не содержит ни одного пустого слова

(2) является строго контекстным

(3) имеет пустые слова

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