Preview an bn

  • Make state final: double click or use context-menu
  • Create new transition: hover over circle, drag from appearing outer circle to target state
  • Edit transitions:
    • Double click on transition label
    • Enter one transition per line
    • Click anywhere else to finish editing
  • Transition format : "a,X/Y", where
    • "a" is alphabet-symbol or epsilon --> epsilon is represented by E
    • "Y" is arbitrary sequence of stack symbols (if the transition only pops from the stack, "Y" is left empty)
    • Example: reading alphabet-symbol "b" with stack "->XXZ" and following a transition "b,X/YX" results in the stack "->YXXZ"
    • Example: reading alphabet-symbol "b" with stack "->XXZ" and following a transition "b,X/" results in the stack "->XZ"
    • Transition of wrong format are ignored
  • Error marking of transitions:
    • Line is marked red, if any error occurs in the transitions
    • Transition is marked red, if it contains symbols that are not in the alphabet respectively stack-alphabet
    • Transition is marked green, if it violates the determinism-condition
    • Lines white --> all right
  • Delete transition or state: use context-menu
  • Move transitions to another state:
    • Drag the line on the side you want to move to another state
    • If there are already transitions, both are merged

Problem

Construct a PDA that recognizes the following language:

{a^n b^n | n > 0}


Hint: To get the maximum number of points, use as few states and non-terminals as possible!