Рубрики

Теория автоматов | Комплект 6

На экзамене GATE CS 2010 были заданы следующие вопросы.

1) Пусть L = {w ∈ (0 + 1) * | w имеет четное число 1 с}, т.е. L — это множество всех битовых строк с четным числом 1 с. Какое из регулярных выражений ниже представляет L?
(А) (0 * 10 * 1) *
(B) 0 * (10 * 10 *) *
(С) 0 * (10 * 1 *) * 0 *
(D) 0 * 1 (10 * 1) * 10 *

Ответ (Б)
Опция (A) неверна, потому что она не может принять «110»
Опция (C) неверна, потому что она принимает строку с одним 1.
Опция (D) неверна, потому что она не может принять 11101

2) Пусть L1 — рекурсивный язык. Пусть L2 и L3 будут рекурсивно перечислимыми, но не рекурсивными языками. Какое из следующих утверждений не обязательно верно?
(A) L2 — L1 рекурсивно перечислимо.
(B) L1 — L3 рекурсивно перечислим
(C) L2 ∩ L1 рекурсивно перечислим
(D) L2 ∪ L1 рекурсивно перечислимо

Ответ (Б)

3) Рассмотрим языки L1 = {0 i 1 j | i! = j}, L2 = {0 i 1 j | i = j}, L3 = {0 i 1 j | i = 2j + 1}, L4 = {0 i 1 j | я! = 2j}. Какое из следующих утверждений верно?
(A) Только L2 не зависит от контекста
(B) Только L2 и L3 являются контекстно-свободными
(C) Только L1 и L2 являются контекстно-свободными
(D) Все являются контекстно-свободными

Ответ (D)
Автоматы Pushdown могут быть созданы для всех четырех языков.

4) Пусть w — любая строка длины n, равная {0,1} *. Пусть L будет множеством всех подстрок w. Каково минимальное количество состояний в недетерминированном конечном автомате, который принимает L?
(А) н-1
(B) n
(С) n + 1
(D) 2n-1

Ответ (С)
Нам нужно минимум n + 1 состояний для построения NFA, который принимает все подстроки двоичной строки. Например, следующий NFA принимает все подстроки «010» и имеет 4 состояния.

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Теория автоматов | Комплект 6

0.00 (0%) 0 votes