Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 33

Рассмотрим нижеприведенный автомат (PDA), который работает над входным алфавитом (a, b, c). Он имеет алфавит стека {Z 0 , X}, где Z 0 — маркер нижней части стека. Набор состояний КПК: (s, t, u, f}, где s — начальное состояние, а f — конечное состояние. КПК принимает конечное состояние. Приведенные ниже переходы КПК изображены стандартным образом. Например, переход (s, b, X) → (t, XZ 0 ) означает, что если КПК находится в состоянии s и символ на вершине стека равен X, то он может прочитать b из ввода и перейдите в состояние t после того, как вы подняли вершину стека и поместили символы Z 0 и X (в этом порядке) в стек.
(s, a, Z 0 ) → (s, XXZ 0 )
(s, ϵ, Z 0 ) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t, .ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z 0 ) → (f, ϵ)

Язык, принятый КПК,
(A) {a l b m c n | l = m = n}
(B) {a l b m c n | l = m}
(C) {a l b m c n | 2l = m + n}
(D) {a l b m c n | т = п}

Ответ: (с)
Объяснение: Каждый вход 'a' вставляет два X в стек, и каждый X может использоваться только 'b' или 'c'. На входе «а» нет правила, которое дает ϵ. Таким образом, для каждого «a» завершение выполняется с помощью «b» или «c» или обоих.

Пример:
Входные данные:
а 3 б 2 с 4
Стек: Z 0
После трех:
стек:
XXXXXXZ 0
После двух б:
стек:
XXXXZ 0
После четырех с:
Вы можете достичь конечного состояния.
a 3 b 2 c 4 также принимается здесь.
Тест на этот вопрос

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

ВОРОТА | GATE IT 2006 | Вопрос 33

0.00 (0%) 0 votes