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

Упражнение 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) к свойствам замкнутости класса контекстно-свободных языков не относят замкнутость относительно деления

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