DPDA - a language that contains the same number of A and B

Question

I need help with creating Deterministic pushdown automaton for language: L = {v1w | v, w ∈ {a, b, c}*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string.

In the first state, I try to load the first string v. But I do not know how to control the same number of "a" and "c" characters.

Thanks for help

Answer 1

Your language:

L = {v1w | v, w in {a, b, c}* and #a(v) = #c(w)}

The first thing to notice is that bs and cs in the first part of the string can be ignored, whereas as and bs in the second part of the string can be ignored. In the first part of the string, push onto the stack; and in the second part of the string, pop off. You know you've moved from the first part of the string to the second when you read a 1. Reject if you (a) run out of stack before you're done seeing cs in the second part of the string or (b) if you still have stuff on the stack when you're done reading the second part of the string. If you run out of input with an empty stack, accept. Something like this:

Q    s    S    |    Q'    S'
---------------+---------------
// first part of the string
---------------+---------------
q0   a    Z/a  |    q0    aZ/aa
q0   b    Z/a  |    q0    Z/a
q0   c    Z/a  |    q0    Z/a
---------------+---------------
// transition to 2nd part
---------------+---------------
q0   1    Z/a  |    q1    Z/a
---------------+---------------
// second part of the string
---------------+---------------
q1   a    Z/a  |    q1    Z/a
q1   b    Z/a  |    q1    Z/a
q1   c    a    |    q1    -

We can define acceptance to be by empty stack in state q1. If you want a separate accepting state you can add a new one and an empty transition for that purpose, although that results in a non-deterministic PDA. We can get a DPDA with a separate accepting state if we really want to as follows:

1. read bs and cs in a loop on the initial state (accepting).
2. if you read an a, go to state A. In state A, read bs and cs in a loop, and if you read as, push as onto the stack.
3. from the initial, upon seeing 1, go to state E, which is accepting, and loop on bs and cs. Crash on an a, or transition to a dead state.
4. from A, upon seeing 1, go to state C read as and bs in a loop, and if you read c with an a on the stack, pop the a. If you read a c with Z on top of the stack, transition to B.
5. state B loops to itself on a and b and crashes, or transitions to a dead state, on c.