Есть ли в этом языке Pushdown Automata (PDA)?

язык: { An B(2n) Cn | где n>=0 }

Я думаю, что да, потому что вы можете обработать это следующим образом: нажать A, нажать B, для каждого C трижды выталкивать из стека, если нет C и стек пуст, вернуть true, иначе вернуть false.


context-free-grammar formal-languages
person Bardya Momeni    schedule 10.05.2013    source источник
comment
Вы, вероятно, получите лучшие ответы здесь: cstheory.stackexchange.com   -  person jpaugh    schedule 11.05.2013
comment
@jpaugh- Это, вероятно, лучше на cs.stackexchange.com, так как cstheory предназначена для вопросов CS исследовательского уровня.   -  person templatetypedef    schedule 11.05.2013

Ответы (2)


arrow_upward
4
arrow_downward

Используйте лемму о накачке, чтобы доказать, что это не контекстно-свободный язык.

Рассмотрим s = ap b2p cp
Затем рассмотрим vxy, |vxy|<=p, |vy|>0 и uvixy iz в L
У нас есть возможности

  1. vxy = aj, j‹=p
  2. vxy = aj bk, j+k‹=p
  3. vxy = bj, j‹=p
  4. vxy = bj ck, j+k‹=p
  5. vxy = cj, j ‹=p

В любом случае констант u и v с.т. не существует. строка находится в L, потому что в vxy может быть только два символа, и тогда нам потребуется переменное количество третьего, чтобы оно отображалось в up u или v

Предложенные вами автоматы терпят неудачу на AAAC, возвращая true. Это не гарантирует, что у вас в два раза больше B, чем A.

person Jean-Bernard Pellerin    schedule 10.05.2013
comment
спасибо, теперь я понял, я могу думать об этом языке так: A^n B^n B^n C^n , и тогда мы теряем 'n' при появлении первых B... - person Bardya Momeni; 14.05.2013

arrow_upward
3
arrow_downward

Такого КПК не существует, потому что этот язык не является контекстно-свободным. Вот краткое доказательство этого. Это основано на том факте, что контекстно-свободные языки закрыты при обратном гомоморфизме (как указано на этих слайдах).

Учитывая язык L = { AnB2nCn | n в N }, рассмотрим гомоморфизм h, определенный из

  • h(A) = A
  • h(B) = BB
  • h(C) = C

Обратным к этому гомоморфизму применительно к L является язык h-1(L) = { x in * | h(x) L }. Глядя на выбор h, это язык { AnBnCn | п в N}. Этот язык является каноническим примером неконтекстно-свободного языка. Однако КЛЛ замкнуты относительно обратного гомоморфизма, поэтому, поскольку h-1(L) не является контекстно-свободным, L не может быть контекстно-свободным. Поэтому КПК для него нет.

Надеюсь это поможет!

person templatetypedef    schedule 10.05.2013
comment
Я бы тоже хотел пометить ваш ответ как окончательный, но я не могу... спасибо... - person Bardya Momeni; 14.05.2013