Design a Push Down Automata to count the number of characters

2
votes

The Alphabet: a, b, c I'm trying to define a PDA which accepts

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

I think some strings that would be accepted are: #abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# etc The number of a's, b's and c's are not necessarily equal.

Start the head of the push down automata on the black space that is right most.

Usually I write my PDAs in columns:

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

and so on...

2
context-free-grammarturing-machinespushdown-automaton
a^n b^n c^n - You are correct. #cab# is not acceptable – Bobby S
Am I misreading this, or is m an unnecessary alias for k? – jball
Nope, I believe you are reading that correct – Bobby S
@Bobby: I edited your question to be more consistent with your update to the language definition. I hope I haven't misunderstood your meaning, if so feel free to roll back. – Jim Lewis
@Jim: Thanks, I didn't see those strings, thanks. This is still not a context free language though correct? – Bobby S

2 Answers

2
votes

I think the language you describe is not context-free, and therefore cannot be recognized with a PDA. The problem is that you need to enforce a constraint (n+p = 2m) that spans an arbitrarily long substring, yet is not allowed to "pump" (when attempting to construct a proof using the pumping lemma for context-free languages).

2
votes
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)
}