Find the pushdown automata of this language L={A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) } with one stack

Question

I can't find the automata because I can only imagine it with multiple stacks or with intersections of set theory.

Answer 1

The language: L = { A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) }

This language is the union of two languages L' and L'':

L'  = { A^i B^j C^k | 2k <= i <= 3k }
L'' = { A^i B^j C^k | j != (i+k) }

If we figure out NPDAs for each of these languages, we can write down a new NPDA for the union of these two languages by:

1. introducing a new start state, q*
2. adding transitions f(q*,e,Z) = (q0',Z) and f(q*,e,Z) = (q0'',Z) where e is epsilon/lambda, Z is the bottom of stack symbol and q0' and q0'' are the start states of NPDAs for L' and L'', respectively.

We have decomposed the harder problem into two simpler problems, and figured out how to put the answers to the easier problems together to answer the harder problem. This is the most important skill you can possibly develop when it comes to formal sciences such as computer science, mathematics and, to a large extent, computer programming.

What should a NPDA for L' look like? It can read any number of Bs at all, provided they come in between As and Cs. We need to keep track of how many As we see, say by pushing an A onto the stack each time we see one; and we need to pop As off the stack once we start seeing Cs. Assuming we want to accept by empty stack, we need to remove all the As; but how do we know how many to remove? If we had 2k = i, we would remove two As for every C we see. If we had i = 3k, we would remove three As for every C we see. As it is, we are somewhere in between. This is conceptually difficulty. The notion of nondeterminism - the N in NPDA - is crucial here. We don't need to know exactly how the string will get accepted; we just need a process that can accept a string in the language, and can't accept one not in the language. We can guess whether we need to remove two or three As from the stack at any particular juncture; this will guarantee we don't exceed the 2k and 3k bounds, and it will also allow us to get any result in between. To make this work, we can simply crash or reject all failed executions of valid strings, provided one of the possible executions passes.

Here is a NPDA based on this description, assuming acceptance by empty stack and accepting state:

Q    s    S    Q'    S'
------------------------
// read A's and push onto stack
q0   A    Z    q0    AZ
q0   A    A    q0    AA

// begin reading B's
q0   B    Z    q1    Z
q0   B    A    q1    Z

// begin reading C's if no B's
q0   C    A    q2    -
q0   C    A    q3    -

// read B's
q1   B    Z    q1    Z
q1   B    A    q1    A

// begin reading C's if B's
q1   C    A    q2    -
q1   C    A    q3    -

// pop the final A for the last C read
q2   -    A    q4    -

// if popping three A's, pop the middle A
q3   -    A    q2    -

// pop the first A for each C read after the first C
q4   C    A    q2    -
q4   C    A    q3    -

// transition to separate accepting state if stack empty
q4   -    Z    qA    -

In the above NPDA, transitions that would lead to a "dead" state are not shown. If you want to show it, add those transitions and call the state qR. In the absence of those explicit transitions, the NPDA is customarily understood to "crash" and reject the input. For any string in L', there will be a way through this NPDA that ends in state qA with an empty stack.

For the other language, we can break it down further. L'' is the union of two languages R' and R'':

R'  = { A^i B^j C^k | j < i + k }
R'' = { A^i B^j C^k | j > i + k }

Using the same construction outlined above, we can create a NPDA for L'' by finding NPDAs for R' and R'' and putting those answers together.

For R', we can push As into the stack when we read As; we can pop As, if any, or push Bs otherwise, when reading Bs; and, finally, we can pop Bs, if any, or push Cs otherwise, when reading Cs. We will have j < i + k if and only if there is either an A or C on top of the stack when we're done. Then, we can move to the accepting state and pop As and Cs from the stack to get an empty stack.

For R'', we can do the same thing and look for a B on top of the stack. We can move to an accepting state and pop Bs to clear the stack.

    R'                             R''

Q    s    S    Q'    S'        Q    s    S    Q'    S'
-----------------------        -----------------------
// count A's, first B/C        // count A's, first B/C
q0'  A    Z    q0'   AZ        q0'' A    Z    q0''  AZ
q0'  A    A    q0'   AA        q0'' A    A    q0''  AA
q0'  B    Z    q1'   BZ        q0'' B    Z    q1''  BZ
q0'  B    A    q1'   -         q0'' B    A    q1''  -
q1'  C    Z    q2'   CZ        q0'' C    A    q2''  CZ
q1'  C    A    q2'   CA        q0'' C    Z    q2''  CA

// count B's, first C          // count B's, first C
q1'  B    Z    q1'   BZ        q1'' B    Z    q1''  BZ
q1'  B    A    q1'   -         q1'' B    A    q1''  - 
q1'  B    B    q1'   BB        q1'' B    B    q1''  BB
q1'  C    Z    q2'   CZ        q1'' C    Z    q2''  CZ
q1'  C    A    q2'   CA        q1'' C    A    q2''  CA
q1'  C    B    q2'   CB        q1'' C    B    q2''  CB

// count C's                   // count C's
q2'  C    Z    q2'   CZ        q2'' C    Z    q2''  CZ
q2'  C    A    q2'   CA        q2'' C    A    q2''  CA
q2'  C    B    q2'   -         q2'' C    B    q2''  -
q2'  C    C    q2'   CC        q2'' C    C    q2''  CC

// accept if A's or C's        // accept if B's
q2'  -    A    qA'   -         q2'' -    B    qA'-  -
q2'  -    C    qA'   -

// accept if A's or C's        // accept if B's
qA'  -    A    qA'   -         qA'' -    B    qA''  -
qA'  -    C    qA'   -

A NPDA for your original language is therefore the following:

Q    s    S    Q'    S'
-----------------------
q*   -    Z    q0    Z
q*   -    Z    q0'   Z
q*   -    Z    q0''  Z

Add to this all the other transitions given earlier and define acceptance to be by empty stack in any of the three accepting states qA, qA' or qA''.