игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Математическая теория формальных языков / Тест 11

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

Упражнение 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