Този език има ли 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 s.t. низът е в L, защото може да има само два символа в vxy и тогава ще ни трябва променливо количество от третия, за да се покаже в u или v

Предложените от вас автомати се провалят на AAAC, връщайки true. Това не гарантира, че имате два пъти повече Б от А.

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

Не съществува такъв PDA, защото този език не е контекстно-свободен. Ето едно кратко доказателство за това. Това се основава на факта, че контекстно-свободните езици са затворени при обратен хомоморфизъм (както е споменато в тези слайдове).

Даден е езикът 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 в N}. Този език е каноничен пример за език без контекст. Въпреки това CFL са затворени при обратен хомоморфизъм, така че тъй като h-1(L) не е контекстно-свободен, L не може да бъде контекстно-свободен. Следователно няма PDA за него.

Надявам се това да помогне!

person templatetypedef    schedule 10.05.2013
comment
Бих искал да отбележа и вашия отговор като окончателен, но не мога... благодаря... - person Bardya Momeni; 14.05.2013