Рубрики

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

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

1) S -> aSa | BSB | | b; язык, сгенерированный вышеуказанной грамматикой над алфавитом {a, b}, представляет собой набор
(А) Все палиндромы.
(B) Все палиндромы нечетной длины.
(C) Строки, которые начинаются и заканчиваются одним и тем же символом
(D) Все четные палиндромы.

Ответ (Б)
Строки, принятые языком: {a, b, aaa, bbb, aba, bab, ..}. Все эти строки имеют палиндромы нечетной длины.

2) Какой из следующих языков над алфавитом {0,1} описывается регулярным выражением: (0 + 1) * 0 (0 + 1) * 0 (0 + 1) *?
(A) Набор всех строк, содержащих подстроку 00.
(B) Множество всех строк, содержащих не более двух нулей.
(C) Множество всех строк, содержащих как минимум два 0.
(D) Множество всех строк, которые начинаются и заканчиваются либо 0, либо 1.

Ответ (С)
Регулярное выражение имеет два 0, окруженных (0 + 1) *, что означает, что принятые строки должны иметь как минимум 2 0.

3) Что из следующего является ЛОЖНЫМ?
(A) Существует уникальный минимальный DFA для каждого обычного языка
(B) Каждый NFA может быть преобразован в эквивалентный PDA.
(C) Дополнение к любому контекстно-свободному языку является рекурсивным.
(D) Каждый недетерминированный КПК может быть преобразован в эквивалентный детерминированный КПК.

Ответ (D)
Детерминированный PDA не может обрабатывать языки или грамматики с неоднозначностью, но NDPDA может обрабатывать языки с неоднозначностью и любой контекстно-свободной грамматикой. Таким образом, каждый недетерминированный КПК не может быть преобразован в эквивалентный детерминированный КПК.

4) Сопоставьте все элементы в группе 1 с правильными параметрами из тех, которые указаны в группе 2.

Group 1                          Group 2
P. Regular expression        1. Syntax analysis
Q. Pushdown automata         2. Code generation
R. Dataflow analysis         3. Lexical analysis
S. Register allocation       4. Code optimization

(А) С-4. Q-1, R-2, S-3
(Б) С-3, Q-1, R-4, S-2
(С) С-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

Ответ (Б)

5) Пусть L = L1 ∩ L2, где L1 и L2 — языки, как определено ниже:
L1 = {a m b m ca n b n | m, n> = 0}
L2 = {a i b j c k | i, j, k> = 0}
Тогда L

(А) не рекурсивный
(B) Обычный
(C) Контекстно-свободный, но не регулярный
(D) Рекурсивно перечислимый, но не контекстно-свободный.

Ответ (С)
Язык L1 принимает строки {c, abc, abcab, aabbcab, aabbcaabb,…} и L2 принимает строки {a, b, c, ab, abc, aabc, aabbc,…}. Пересечение этих двух языков: L1 ∩L2 = {a k b k c | k> = 0}, которая не зависит от контекста, но не является регулярной.

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

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

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

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

0.00 (0%) 0 votes