Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 40

Какая из следующих строк не является членом L (M)?

(А) ааа
(B) Aabab
(С) бааба
(D) Баб

Ответ: (с)
Объяснение:
Основы КПК
Автоматы, работающие по принципу push-down или PDA, по сути являются NFA со стеком, и их функция перехода также зависит от символа на вершине стека. Формально PDA — это 6-кортеж (Q, Σ, Γ, δ, q0, F), где Q — множество всех возможных состояний, Σ — множество всех возможных входных данных, Γ — множество всех возможных символов стека, δ: Q × Σ × Γ → Q × Γ — функция перехода, q0 — начальное состояние, и
F ⊆ Q — множество конечного состояния.

Иногда известно, что PDA состоит из 7 кортежей, когда мы рассматриваем начальный символ стека z0 как дополнительный элемент в
выше 6 кортежей. Обратите внимание, что должна существовать функция перехода для данного входа, иначе не будет никакого возможного перемещения.

КПК может быть двух типов: КПК, принимающий пустой стек, и КПК в конечном состоянии.

КПК, принимающие пустой стек, — это КПК, для которых принят данный ввод, если в заданной входной строке, когда вход исчерпан, стек должен быть пустым.

Аналогично, конечное состояние, принимающее PDA, представляет собой PDA, для которого данный вход принят, если в данной входной строке, когда вход исчерпан, PDA должен находиться в одном из конечных состояний.

Недетерминированный КПК или NPDA — это КПК, в котором для данного входа возможен множественный выход. т.е. функция перехода δ отображает заданный входной сигнал из Q × Σ × Γ в конечный набор Q × Γ.

Для данного вопроса
, поскольку существует более одного выхода, соответствующего данному входу для функции перехода, мы рассмотрим NPDA для выполнения ввода и остановим выполнение для соответствующей ветви, если нет возможности переместить заданный ввод и мы предполагаем, что если машина останавливается в одном из конечных состояний и ввод исчерпан, мы принимаем строку, в противном случае мы ее отклоняем. Обратите внимание, что данный PDA является конечным состоянием, принимающим PDA, а не пустым стеком, принимающим PDA.

Выбор вопросов:

Мы будем предполагать, что начальный символ стека ε, и

В варианте 1 исполнение будет следующим:
(s, a,) → (s, a) или (f, ε).
Давайте сначала рассмотрим (s, a) как выходные данные и выполним оставшиеся входные данные. (s, a, a) → Нет действительного перемещения. Остановить эту ветку и не в конечном состоянии, поэтому не принято. Теперь рассмотрим (f, ε) как вывод. (f, a, ε) → Нет допустимого перемещения.
остановите эту ветвь. Обратите внимание, что КПК находится в одном из конечных состояний, но входная строка не исчерпана, поэтому это не должно быть принято КПК.

При выборе 2 «Выполнение» начнется с выбора 1 и остановится на персонаже 2, поскольку невозможно двигаться. Эта опция также не принимается так же, как и в первом варианте.
3

В варианте 3 исполнение будет следующим:
(s, b, ε) → (s, a). (s, a, a) → Невозможный ход. остановить эту ветку . Поскольку остановлено до достижения какого-либо конечного состояния, эта опция не принимается.

В варианте 4 эта опция также не принимается, так как КПК останавливается на втором символе, как и в предыдущей опции. Эта опция также не принимается.

Предполагая, что если КПК останавливается на входе из-за невозможности перемещения и если текущее состояние является одним из конечного состояния, но вход не исчерпан, КПК отклонит эту строку. Для Вопроса 2 каждый ответ верен, т.е. данное для строки принадлежит языку данного PDA.

Опять же, предполагая, что если КПК останавливается на входе из-за невозможности перемещения и если текущее состояние является одним из конечного состояния, но вход не исчерпан, КПК будет продолжать потреблять входную строку до тех пор, пока не придет конец строки, Строка в опции (A) и опции (B) будет принята языком этого КПК. в то время как вариант (C) и вариант (D) по-прежнему не будут приняты к концу
строки, КПК не будет в конечном состоянии. Таким образом, учитывая это предположение, вариант (C) и вариант (D) будут верны для этого вопроса.

Это объяснение предоставлено Дургешем Пандей.
Тест на этот вопрос

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

ВОРОТА | GATE-IT-2004 | Вопрос 40

0.00 (0%) 0 votes