Рубрики

Теория автоматов | Набор 4

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

1) Пусть P — регулярный язык, а Q — язык без контекста, такой что Q ⊆ P. (Например, P — язык, представленный регулярным выражением p * q *, а Q — {p n q n | n ∈ N}). Тогда что из следующего ВСЕГДА регулярно?
(A) P ∩ Q
(B) P — Q
(С) ∑ * — P
(D) ∑ * — Q

Ответ (С)
Выражение ∑ * — P представляет собой дополнение к P, который является регулярным языком. Дополнение регулярных языков также является регулярным. Тогда DFA, который принимает дополнение к L, т. Е. — * — L, может быть получен путем замены принимающих его состояний на непринятые.

2) Рассмотрим язык L1, L2, L3, как указано ниже.
L1 = {0 p 1 q | p, q ∈ N}
L2 = {0 p 1 q | p, q ∈ N и p = q}
L3 = {0 p 1 q 0 r | p, q, r ∈ N и p = q = r}
Какое из следующих утверждений не верно?

(A) Автоматы Push Down (PDA) могут использоваться для распознавания L1 и L2
(B) L1 — обычный язык
(C) Все три языка не зависят от контекста
(D) Машина Тьюринга может использоваться для распознавания всех трех языков

Ответ (С)
Язык L3 не является контекстно-свободным. Обратитесь к этому для более подробной информации.

3) Определение языка L с алфавитом {a} дается следующим образом. L = {a nk | k> 0, а n — положительная целочисленная константа. Какое минимальное количество состояний требуется DFA для распознавания L?
(A) k + 1
(B) n + 1
(С) 2 н + 1
(D) 2 k + 1

Ответ (Б)
Обратите внимание, что n — это константа, а k — любое положительное целое число. Например, если n задано как 3, тогда DFA должен быть в состоянии принять 3a, 6a, 9a, 12a, .. Чтобы построить такой DFA, нам нужно 4 состояния.

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

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

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

Теория автоматов | Набор 4

0.00 (0%) 0 votes