Рубрики

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

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

1) Что является дополнением к языку, принятому NFA, как показано ниже? Предположим, что ∑ = {a} и ε — пустая строка

(А) Ф
(B) ε
(С)
(D) {a, ε}

Ответ (Б)
Данный алфавит ∑ содержит только один символ {a}, и данный NFA принимает все строки с любым числом вхождений 'a'. Другими словами, NFA принимает +. Поэтому дополнением к языку, принимаемому автоматами, является пустая строка.

2) Учитывая язык L = {ab, aa, baa}, какая из следующих строк находится в L *?
… .1) абаабааабаа
… .2) аааабаааа
… .3) baaaaabaaaab
… .4) baaaaabaa

(А) 1, 2 и 3
(Б) 2, 3 и 4
(С) 1, 2 и 4
(D) 1, 3 и 4

Ответ (С)
Любая комбинация строк в множестве {ab, aa, baa} будет в L *.
…. 1) «abaabaaabaa» может быть разделен как комбинация строк в множестве {ab, aa, baa}. Перегородки «ab aa baa ab aa»
…. 2) «aaaabaaaa» может быть разделен как комбинация строк в множестве {ab, aa, baa}. Перегородки «аа аа аа аа»
…. 3) «baaaaabaaaab» не может быть разделен как комбинация строк в множестве {ab, aa, baa}
…. 4) «baaaaabaa» может быть разделен как комбинация строк в множестве {ab, aa, baa}. Перегородки «baa aa ab aa»

3) Какие из следующих проблем разрешимы?
… .1) Дает ли данная программа вывод?
… .2) Если L — контекстно-свободный язык, то является ли L '(дополнение к L) также контекстно-свободным?
… .3) Если L регулярный язык, то L 'также регулярен?
… .4) Если L — рекурсивный язык, то является ли L 'также рекурсивным?

(А) 1, 2, 3, 4
(Б) 1, 2,
(С) 2, 3, 4
(D) 3, 4

Ответ (D)
…. 1) Разновидность проблемы остановки машины Тьюринга, и она неразрешима.
…. 2) Языки без контекста не закрываются на пересечении и дополнении. Смотрите это для деталей.
…. 3) Дополнение регулярных языков также является регулярным. Тогда DFA, который принимает дополнение к L, т. Е. — * — L, может быть получен путем замены принимающих его состояний на непринятые.
…. 4) Рекурсивные Языки закрыты в дополнении. Смотрите это для деталей.

4) Рассмотрим набор строк на {0,1}, в котором каждая подстрока из 3 символов имеет не более двух нулей. Например, 001110 и 011001 на языке, а 100010 — нет. Все строки длиной менее 3 также на языке. Частично заполненный DFA, который принимает этот язык, показан ниже.

Недостающие дуги в DFA

Ответ (D)
Состояние 'q' является состоянием ловушки. Все остальные государства являются принимающими государствами. В состоянии 00 DFA должен перейти в 'q' для входного символа 0. Все (не перехватывающие) состояния указывают на имена, обозначающие символы, увиденные до достижения этого конкретного состояния. Вариант (D) является единственным вариантом, который следует этим правилам.

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

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

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

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

0.00 (0%) 0 votes