Рубрики

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

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

1. Пусть S и T — язык над = {a, b}, представленный регулярными выражениями (a + b *) * и (a + b) * соответственно. Какие из следующих утверждений верно? (GATE CS 2000)

(а) ScT (S является подмножеством T)
(б) TcS (T является подмножеством S)
(с) S = T
(d) SnT = Ø

Ответ: (с).


2. Пусть L обозначает язык, сгенерированный грамматикой S — OSO / 00. Какие из следующих утверждений верно? (GATE CS 2000)

(а) L = O
(б) L регулярно, но не O
(c) L не зависит от контекста, но не является регулярным
(d) L не является контекстно-свободным

Ответ: (б)
Объяснение: Обратите внимание, что сама грамматика не является регулярной, но язык L является регулярным, поскольку L можно представить с помощью обычной грамматики, например, S -> S00 / 00.
Ссылки:
http://en.wikipedia.org/wiki/Regular_grammar


3. Рассмотрим следующие два утверждения:
S1: {0 ^ 2n | n> = l} — обычный язык
S2: {0 ^ m 0 ^ n 0 ^ (m + n) lm> = 1 и n> = 2} является обычным языком
Какое из следующих утверждений является правильным? (GATE CS 2001)
а) правильно только S1
б) правильно только S2
в) S1 и S2 верны
г) Ни один из S1 и S2 не является правильным

Ответ: (с)
Объяснение:
S1 может быть записано как (00) ^ n, где n> = 1. А S2 может быть записано как (00) ^ (m + n), где m> = 2 и n> = 1. S2 может быть дополнительно уменьшено до (00 ) ^ x, где x> = 3.
Мы можем легко написать регулярные грамматики для S1 и S2.
G1 -> G100 / 00 (для S1)
G2 -> G200 / 000000 (для S2)


4. Какое из следующих утверждений верно? (GATE CS 2001)

(a) Если язык не зависит от контекста, он всегда может быть принят детерминированным автоматом
(б) Объединение двух контекстно-свободных языков является контекстно-свободным
(c) Пересечение двух контекстно-свободных языков является контекстно-свободным
(d) Дополнение к контекстно-свободному языку является контекстно-свободным

Ответ: (б)
Объяснение:
Контекстные языки закрыты для следующих операций. То есть, если L и P являются контекстно-свободными языками, а D является обычным языком, следующие языки также не зависят от контекста:
• Клини звезда L * L
• изображение Ø (L) L под гомоморфизмом Ø
• конкатенация L и P
• союз Л и П
• пересечение L с регулярным языком D (L n D).
Контекстно-свободные языки не закрываются под дополнением, пересечением или различием.
Почему а) не соответствует действительности?
Язык, распознаваемый детерминированным автоматом, является языком, детерминированным без контекста. Не все контекстно-свободные языки являются детерминированными. Это не похоже на ситуацию для детерминированных конечных автоматов, которые также являются подмножеством недетерминированных конечных автоматов, но могут распознавать тот же класс языков (что демонстрируется конструкцией подмножества).
Ссылки:
http://en.wikipedia.org/wiki/Context-free_language
http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton


5. Для произвольного недетерминированного конечного автомата (NFA) с N состояниями максимальное число состояний в эквивалентном минимизированном DFA не меньше. (GATE CS 2001)
(а) N ^ 2
(б) 2 ^ N
(с) 2N
(г) N!

Ответ: (б)
Ссылки:
http://en.wikipedia.org/wiki/Powerset_construction

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

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

0.00 (0%) 0 votes