Какой язык поддерживает этот Pushdown Automata (PDA)?

Question

Экзамен завтра и проф дайте нам знать вопрос, который будет на нем :).

В контексте этой диаграммы L - epsilon (пустая строка), а Z0 - пустой символ стека.

Я достиг определенного прогресса в определении нескольких правил для слов, которые генерирует язык, но не смог определить весь язык.

Спасибо!

Answer 1

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

1. Предположим, что ввод начинается с ab. Затем мы переходим в состояние 2 с пустым стеком, поэтому правило «L» не совпадает, поэтому мы находимся только в состоянии 2.

2. Предположим, что ввод начинается с (a^n)b для n> 1. Затем мы переходим в состояние 2 с a^(n-1) в стеке, и правило "L" запускает нас, возвращая нас в состояние 1 с a^(n-2) в стеке. Но так как стек в состоянии 2 равен a^(n-1) (и n> 1), стрелки обратного цикла в состоянии 2 не могут совпадать ... Так что и здесь мы (фактически) находимся (фактически) только в одном состоянии: состояние 1.

3. Предположим, что ввод начинается с ba. Затем мы снова переходим в состояние 2 с пустым стеком, и, как и в случае (1), правило «L» не совпадает, поэтому мы находимся только в состоянии 2.

4. Наконец, предположим, что ввод начинается с (b^n)a для n> 1. Затем мы переходим в состояние 2 с b^n в стеке, поэтому правило «L» не срабатывает, и мы только в состояние 2.

Другими словами, всякий раз, когда правило «L» создает «разветвление» КПК в состояние 1, оно делает это только потому, что «a» находилось на вершине стека ... Что означает, что разветвление остается в состояние 2 должно умереть на следующем входном символе. Таким образом, в действительности здесь нет недетерминизма, и вы можете смоделировать этот КПК так, как будто он всегда находится в одном состоянии.

С этим наблюдением, я думаю, довольно легко понять, что @Nayuki верен: этот КПК принимает любую строку с вдвое большим числом a, чем b.

Во-первых, покажите, что, когда КПК находится в состоянии 1, стек всегда полностью состоит из a или полностью из b (или является пустым). А когда КПК находится в состоянии 2, стек полностью состоит из b (или пуст). Это простой анализ случаев, похожий на четыре случая выше; например msgstr "состояние 1, стек = a ^ n, следующий символ b => состояние 1, стек = a ^ (n-2)". (Забота о случаях n = 0 или n = 1.)

Думайте о каждом b как о «желании стать партнером с 2 a s». Состояние 1, стек = a^n означает, что n a s ожидают партнеров. Состояние 1, стек = b^n означает, что n b s ожидают партнеров. Состояние 2, стек = b^n означает, что один b был партнером с одним a , а n b s все еще ожидают партнеров.

Докажите, что то, что я только что написал, верно, и результат следует.

Answer 2

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

Answer 3

Число «а» в два раза больше числа «б».

Точная грамматика:

S  = (a|b)*      where N_a(S)=2*N_b(S)

N_a (X) означает количество 'a в X. и т. Д.

В любой момент времени в стеке могут быть все «а» или все «б». Зачем? потому что нет переходов a / xxbxx или b / xxaxx.

Случай 1: стек - это все "а".

Вы можете увидеть цикл будет иметь вид:

1. a (a * b) +, если в последний раз мы возьмем переход L, a / L в (2-> 1)

2. a (a * b) + a, если в последний раз мы возьмем переход a, Z0 / Z0 в (2-> 1). и последнее 'a' ничего не вытолкнет из стека.

в каждом цикле, число 'a' - два. и номер цикла совпадает с номером «b» (кроме случаев, когда a, Z0 / Z0 произошли в последний раз)

мы возьмем последний переход L, a / L, если число 'a' еще до последнего 'b'

мы возьмем последний переход a, Z0 / Z0, если число «a» будет нечетным перед последним «b». a, Z0 / Z0 принимает еще один 'a'

Таким образом,

A1=a(a*b)+a  where N_a(A1)=2*N_b(A1),     N_a(A1) is even
A2=a(a*b)+   where N_a(A2)=2*N_b(A2),     N_a(A2) is even

Это уменьшит до:

A=a(a|b)+    where N_a(A)=2*N_b(A),     N_a(A) is even

(мы будем в состоянии 1, а стек пуст)

Случай 2: стек - все "b".

Точно так же вы можете видеть, что каждый цикл будет иметь форму: b * ab * a. и в каждом цикле будет выталкиваться ровно один «b». Всякий раз, когда принимается «b», a «b» помещается в стек. Таким образом, когда стек пуст, и мы вернулись в состояние 1, число циклов будет взято равным числу 'b', которые мы приняли / поместили в стек. Таким образом,

B=b(b*ab*a)^n where N_b(B)=n

Но вы можете видеть, n = N_a (B) / 2. Таким образом,

B=b(b*ab*a)+ where N_a(B)=2*N_b(B)

Это уменьшит до:

B=b(b|a)+ where N_a(B)=2*N_b(B)

И так как существует только два возможных пути (A или B), и цикл может быть взят 0 или 1 раз,

Таким образом,

S=(A|B)*
A=a(a|b)+    where N_a(A)=2*N_b(A)
B=b(b|a)+    where N_a(B)=2*N_b(B)

Это уменьшит до:

S=((a|b)+)*   where N_a(S)=2*N_b(S)

, который уменьшится до:

S=(a|b)*      where N_a(S)=2*N_b(S)

1064 * что и требовалось доказать *