How to design a pushdown automata

Question

How would i design a PDA that accepts balanced parenthesis and brackets for instance ([][]), I am having a hard time getting started. I need help writing transition functions for this problem. Any help is appreciated

Answer 1

I normally would not do someone's entire homework for them, but the reality is that when it comes to automata, even if I do, it won't help you much unless you really do understand how these things work and the sad truth is that most schools don't teach them well to begin with.

Let's think about how this PDA operates and forget about states and transitions and whatnot for now: When our PDA gets input it should work like this:

• If there is no input:
  • If the top of the stack is empty (which is often indicated by some special value let's say $ for this example) then our PDA accepts the string: it's a properly balanced string of parentheses and brackets.
  • Otherwise we go to the error state. The string is not a properly balanced string of parentheses and brackets.
• If the input is either an ( or a [ then push the input onto the stack and look at the next input character.
• If the input is a ) then:
  • If the top of the stack is a ( pop the top of the stack, and look at the next input.
  • Otherwise, go to the error state. The string is not a properly balanced string of parentheses and brackets.
• If the input is a ] then:
  • If the top of the stack is a [ pop the top of the state, and look at the next input.
  • Otherwise, go to the error state. The string is not a properly balanced string of parentheses and brackets.

Now, knowing what our PDA has to do let's try to think about how to describe our PDA more formally. We will assume that:

• Τhe set of valid input symbols Σ = { (, ), [ and ] }
• The initial stack symbol Z = $
• Τhe set of valid stack symbols Γ = { (, [ } ∪ Z
• The set of states Q = { q0, ACCEPT, REJECT }
• The initial state q0.

Using a notation similar to what is described on http://en.wikipedia.org/wiki/Pushdown_automaton for PDA state transitions we can think about the states and how things flow:

• (q0, ε, top=$, ACCEPT, nil) This tells our PDA: when you are in state q0 and there is no more input and the top of the stack is a $ go to the ACCEPT state, leaving the stack unchanged.

• (q0, ε, top=(, REJECT, nil) This tells our PDA: when you are in state q0 and there is no more input and the top of the stack is a ( go to the REJECT state, leaving the stack unchanged.

• (q0, ε, top=[, REJECT, nil) This tells our PDA: when you are in state q0 and there is no more input and the top of the stack is a [ go to the REJECT state, leaving the stack unchanged.

• (q0, (, top=top, q0, push () This tells our PDA: when you are in state q0 and the input is a ( then, regardless of what is at the top of the stack, go to the state q0 and push a ( onto the stack.

• (q0, [, top=top, q0, push [) This tells our PDA: when you are in state q0 and the input is a [ then, regardless of what is at the top of the stack, go to the state q0 and push a [ onto the stack.

• (q0, ), top=(, q0, pop) This tells our PDA: when you are in state q0 and the input is a ) and the top of the stack is a ( then go to the state q0, and pop the top of the stack off.

• (q0, ), top=[, REJECT, nil) This tells our PDA: when you are in state q0 and the input is a ) and the top of the stack is a [ then go to the REJECT stack, leaving the stack unchanged.

• (q0, ), top=$, REJECT, nil) This tells our PDA: when you are in state q0 and the input is a ) and the top of the stack is a $ then go to the REJECT stack, leaving the stack unchanged.

• (q0, ], top=[, q0, pop) This tells our PDA: when you are in state q0 and the input is a ] and the top of the stack is a [ then go to the state q0, and pop the top of the stack off.

• (q0, ], top=(, REJECT, nil) This tells our PDA: when you are in state q0 and the input is a ] and the top of the stack is a ( then go to the REJECT stack, leaving the stack unchanged.

• (q0, ], top=$, REJECT, nil) This tells our PDA: when you are in state q0 and the input is a ] and the top of the stack is a $ then go to the REJECT stack, leaving the stack unchanged.

We could have achieved this using more states, but it's interesting to note that one "processing" state is enough.

You may also want to note that depending on your instructor, you may not be required to explicitly add a REJECT state, although it's good form to do so.

I hope this helps.

Answer 2

This might help you get started:

bool check_and_pop(char c) {
  if (top() == c) {
    pop();
    return true;
  }
  return false;
}

int check_input() {
 char c;
 while ((c = getc())) {
  switch (c) {
    case '(': case '{': case '[': push(c); break;
    case ')': 
      if (!check_and_pop('(')
       return REJECT;
      break;
    case '}':
      if (!check_and_pop('{')
       return REJECT;
      break;
    // ...
 }
 // end of input, check the stack to accept/reject
 if (stack_size() == 0)
    return ACCEPT;
 else
    return REJECT;
}