Как узнать язык, который принят ниже NPDA - PullRequest
Новая
       49

Как узнать язык, который принят ниже NPDA

0 голосов
/ 04 февраля 2020

Я хочу понять, как найти язык, который будет принят ниже NPDA. 

M = {Q, Σ, Τ, δ, q0, z, F}
Q is a set of state: {q0, q1, q2}
Σ is alphabet: {a, b}
Τ is stack alphabet: {0, 1, z}
δ is transition function
z is stack start symbol
F is set of final state.

И его функция перехода ниже. 

δ(q0, a, z) = {(q1 , 0), (q2 , λ)}
δ(q1, b, 0) = {(q1, 1)}
δ(q1, b, 1) = {(q1, 1)}
δ(q1, a, 1) = {(q2, λ)}

1 Ответ

1 голос
/ 04 февраля 2020

Основываясь на этих переходах, я буду предполагать, что конечным состоянием является q2, и оно принимает с пустым стеком (похоже, оно избавляется даже от символа нижней части стека z, что немного необычно для меня, но Я думаю, это нормально).

Это следующие переходы: 

δ(q0, a, z) = {(q1 , 0), (q2 , λ)}
δ(q1, b, 0) = {(q1, 1)}
δ(q1, b, 1) = {(q1, 1)}
δ(q1, a, 1) = {(q2, λ)}

Давайте рассмотрим их по одному.

  1. δ(q0, a, z) = {(q1 , 0), (q2 , λ)} означает что если мы находимся в исходном состоянии и видим a, мы можем либо go указать q1 и заменить z на 0, либо мы можем избавиться от z и go заявить q2. Это фактически принимающая конфигурация для NPDA; это означает, что NPDA принимает пустую строку, и любой язык, который мы определяем, также должен содержать эту строку. Поскольку единственный выход из начального состояния q0 состоит в том, чтобы увидеть a, мы также знаем, что любые непустые строки в нашем языке должны начинаться с a.

  2. δ(q1, b, 0) = {(q1, 1)} означает, что если мы сейчас находимся в состоянии q1, видим b на входе и имеем 0 на вершине стека, мы можем изменить символ стека на 1. Мы будем в этой конфигурации, как только мы получим состояние q1 с q0. Обратите внимание, что, поскольку никакой другой переход не помещает 0 поверх стека, это единственный раз, когда этот переход можно использовать; и действительно, его нужно использовать, поскольку q1 не принимает, и мы должны пройти через этот переход, чтобы очистить 0 с вершины стека. Итак, все непустые строки в языке должны начинаться с ab.

  3. δ(q1, b, 1) = {(q1, 1)} означает, что если мы в состоянии q1, см. b на входе и 1 на вершине стека, мы можем потреблять больше b s навсегда. Мы останемся в этой конфигурации, пока у нас будет больше b на входе. Однако нам не обязательно проходить через это состояние: существуют другие переходы, которые помещают 1 поверх стека, и путь к принимающему состоянию может вообще не включать этот переход. Этот переход позволяет нам поставить столько b с, сколько мы хотим, после того, как требуется b, которое мы видели в последнем переходе.

  4. δ(q1, a, 1) = {(q2, λ)} means that if we're in state q1 , see an a in the input and have a 1 on top of the stack, we can erase the stack and go to the accepting state. This means that any non-empty string in the language ends with a single a`.

Напомним:

  1. пустая строка на языке
  2. любая непустая строка в языке начинается с ab
  3. любая непустая строка в языке может иметь произвольное число b с в середине
  4. любая непустая строка в языке заканчивается с a.

Собрав все это вместе, мы находим регулярное выражение, описывающее язык: e + abb*a. Мы не должны удивляться этому, так как этот стек NPDA содержит от одного до двух элементов; поскольку количество используемых стеков является постоянным, NPDA эквивалентен некоторому DFA, и поэтому его язык должен быть регулярным.

...