Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 24

Что из следующего является ИСТИННЫМ?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Пояснение: (A) L = {anbn | n> = 0} не является регулярным, потому что не существует конечного автомата, который может
вывести эту грамматику. Интуитивно, конечный автомат имеет конечную память, следовательно, он не может отслеживать
количество как. Это стандартный КЛЛ, хотя.

(B) L = {anbn | n простое} опять не регулярно, потому что нет способа запомнить / проверить,
текущий п простое или нет. Следовательно, не существует конечного автомата для получения этой грамматики, поэтому он
не регулярно.

(C) L = {w | w имеет 3k + 1 bs} — регулярный язык, потому что k — фиксированная константа, и мы можем легко
эмулировать L как a ∗ ba ∗… ..ba ∗ так, чтобы в каждом b было ровно 3k + 1 bs и a ∗ s
грамматика.

(D) L = {ww | w ∈ Σ ∗} опять не является регулярной грамматикой, фактически это даже не CFG. Здесь нет
способ запомнить и вывести двойное слово, используя конечный автомат.

Следовательно, правильный ответ будет (С).
Это решение предоставлено Винет Пурсвани .
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 24

0.00 (0%) 0 votes