Answer

The reason why we need a stack is to keep track of the number of unmatched left brackets we have accumulated. We don't need it for anything else so the stack alphabet has only one character (which might as well be a left bracket. I know we said the alphabets should be kept disjoint for reasons of hygiene but...!) The PDA starts in the accepting state with an empty stack.

Transition rules are as follows:

  1. If you are in the dead state, stay there whatever happens.
  2. If you are in the accepting state
    (a) if you read a right bracket go to the dead state;
    (b) if you read a left-bracket push it onto the stack and go to the wait-and-see state;
  3. If you are in the wait-and-see state then
    (a) if you read a left bracket push it on the stack and remain in the wait-and-see state;
    (b) if you read a right bracket pop the top character off the stack and stay in the wait-and-see state unless the stack is now empty, in which case go to the accepting state.

Notice that if you are in the wait-and-see state then the stack is not empty, so we don't have to define the transition function for the case when the stack is not empty. Similarly when we are in the accepting state the stack must be empty. These two facts are not hard to see, but are a wee bit tricky to prove. You would have to prove by induction on the length n of possible input strings that for all strings s of length n when the machine has read s then if it's in the wait-and-see state then the stack is not empty and if it is in the accepting state then the stack is empty.

The PDA you have just written is a deterministic PDA.

Back to notes