Разработайте автоматы Push Down для подсчета количества символов

Алфавит: a, b, c Я пытаюсь определить КПК, который принимает

 a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0

Я думаю, что допустимы следующие строки: #abc#; #aabbcc#; #aaabbbccc#; #аббкк#; #aaabbc# и т.д. Количество букв a, b и c не обязательно равно.

Запустите головку автоматов, толкающих вниз, на самой правой черной клетке.

Обычно я пишу свои КПК столбцами:

State:    Symbol Read:    Next State:    Head Instruction:    
s         #               r1             Left
r1        c               r2             #

и так далее...


turing-machines context-free-grammar pushdown-automaton
person Bobby S    schedule 13.11.2010    source источник
comment
a^n b^n c^n - Вы правы. #такси# недопустимо   -  person Bobby S    schedule 13.11.2010
comment
Я неправильно понимаю это, или m является ненужным псевдонимом для k?   -  person jball    schedule 13.11.2010
comment
Нет, я считаю, что вы читаете это правильно   -  person Bobby S    schedule 13.11.2010
comment
@Bobby: я отредактировал ваш вопрос, чтобы он больше соответствовал вашему обновлению определения языка. Надеюсь, я правильно понял ваш смысл, если это так, не стесняйтесь откатывать назад.   -  person Jim Lewis    schedule 13.11.2010
comment
@ Джим: Спасибо, я не видел этих строк, спасибо. Это все еще не контекстно-свободный язык, хотя правильно?   -  person Bobby S    schedule 13.11.2010
comment
@Bobby: Все еще не CF, я почти уверен.   -  person Jim Lewis    schedule 13.11.2010

Ответы (1)


arrow_upward
2
arrow_downward

Я думаю, что язык, который вы описываете, не является контекстно-свободным, и поэтому не может быть распознан с помощью КПК. Проблема в том, что вам нужно наложить ограничение (n+p = 2m), которое охватывает произвольно длинную подстроку, но не позволяет «накачивать» (при попытке построить доказательство с использованием леммы накачки для контекстно-свободных языков).

person Jim Lewis    schedule 13.11.2010
comment
Спасибо, я согласен с вами. Я покажу с помощью леммы о накачке, что это не является контекстно-свободным. - person Bobby S; 13.11.2010