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

Упражнение 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) квадратичная грамматика

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