CODEWITHSUNDEEP
context-free-grammarturing-machinespushdown-automaton
Bobby S
Bobby S

Reputation: 4116

Design a Push Down Automata to count the number of characters

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...

Upvotes: 2

Views: 3524

Answers (2)

muzaffer_aydin
muzaffer_aydin

Reputation: 21

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

Upvotes: 2

Jim Lewis
Jim Lewis

Reputation: 45115

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).

Upvotes: 2

Related Questions