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

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

2 голосов
/ 13 ноября 2010

Алфавит: 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 #;# Abbccc #;# aaabbc # и т. д. Число a, b и c не обязательно равно.

Запустите головку нажимных автоматов на черном пространстве, которое больше всего справа.

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

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

и т. Д ...

Ответы [ 2 ]

2 голосов
/ 21 декабря 2010 
M=(K, E, q0, F, delta, stack_alphabet)
K={q0,q1,q2}
E={a,b,c,z}
F={q2}
stack_alphabet={a,b,z}
delta=
{
 *pop*     *push*
(q0, e, e)(q1, z)
(q1, a, e)(q1, a)
(q1, b, a)(q1, e)
(q1, b, z)(q1, bz)
(q1, c, b)(q2, e)
(q2, c, b)(q2, e)
}
2 голосов
/ 13 ноября 2010

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

...