NPDA for this language with n and n-1

Question

To draw the transition graph of a NPDA that accepts L, I think one could start this problem by reading an a, writing an a, then moving right, then doing the same for b so that there is some state q₁ that is getting those "ab" movements. But then how is it possible to get bb to have n-1?

I have something that I think works but I'm teaching this to myself so maybe someone can show me where the n and n-1 could be done correctly.

EDIT:

But now this should be it --

Answer 1

It's quite simple actually. Each time you read "ab", you store a token in the stack. Then after reading "c", you take one from that token. Then for each "bb", you take one token from the stack. When the stack is empty you accept.

For the NPDA itself, it depends how do you define the acceptance. From your question, I don't get what do you mean by "writing an a, then moving right". Are you confusing NPDA with a Turing Machine? An NPDA is very similar to an NFA (Non-deterministic Finite Automata) except that it's equipped with a stack, in which you can put stack symbols. Read up more here: http://www.cs.duke.edu/~rodger/courses/cps140/lects/sectnpdaH.pdf

Below is the transition table, assuming stack symbols {A,Z} where Z is the initial stack symbol. Accept when we are in the only accepting state q_a and we have finished reading the input tape. Assume that each transition always consume one stack symbol, and if there is no more symbol to be consumed while the NPDA is not in acceptance state, the NPDA does not accept (or reject) the string.

In the table below, the first column represents the state we are currently in and the stack symbol we are reading. Subsequent columns represent the new state and stack symbol pushed to the stack upon reading a particular character in input string (or not reading any character at all with ε)

+------++---------+-------+--------+-------+
|      ||    a    |   b   |   c    |   ε   |
+------++---------+-------+--------+-------+
|(q1,Z)|| (q2,Z)  |    -   |    -   |   -   |
+------++---------+-------+--------+-------+
|(q1,A)|| (q2,A)  |    -   | (q3,ε) |   -   |
+------++---------+-------+--------+-------+
|(q2,Z)||    -    |(q1,ZA) |    -   |   -   |
+------++---------+-------+--------+-------+
|(q2,A)||    -    |(q1,AA) |    -   |   -   |
+------++---------+-------+--------+-------+
|(q3,Z)||    -    |   -    |    -   |(qa,ε) |
+------++---------+-------+--------+-------+
|(q3,A)||    -    | (q4,A) |    -   |   -   |
+------++---------+-------+--------+-------+
|(q4,A)||    -    | (q3,ε) |    -   |   -   |
+------++---------+-------+--------+-------+

The key idea here is that the number of A in the stack represents how many times the phrase "ab" appears in the input string.

You can see that in reading "a" in state q₁ with stack symbol Z, we push back Z to the stack. Meaning there is still no "ab" detected yet. It will then go to q₂.

In q₂, we only accept "b", any other input will cause it to hang (and hence reject). It pushes back the state it read into the stack, plus an additional A, effectively increasing the number of A in the stack by 1, since this transition represents an additional phrase "ab" in the input string.

The state q₃ represents the part after successfully reading "c". Note that transition from q₁ to q₃ must consume A, not Z, since we have the constraint n >= 1. Then, upon reading "b", it will go to state q₄ to wait for another "b". Later q₄, upon reading "b", will consume the stack symbol A, matching

At state q₃ we also want a transition to acceptance state q_a once we reach stack symbol Z, referring to the state where there are n copies of "ab" and n-1 copies of "bb".

State q₄ only accepts the input string "b" with stack symbol A, representing finding a new phrase "bb" should match one phrase "ab" previously found.

Hope this helps!