Sample PDA Inputs

These examples are for use with the perl PDA emulator provided at the bottom of Context Free Languages. That page also contains a description of what a PDA is and how it works.

The specification for a machine that accepts any string of the form $\{a^{n}b^{n}|n\geq 0\}$ :

:States:
q1 q2 q3 q4
:Start State:
q1
:Accept States:
q4
:alphabet:
a b
:stack alphabet:
$ a
:rules:
q1 e e q4 $
q1 e e q2 $
q2 b a q3 e
q2 a e q2 a
q3 b a q3 e
q3 e $ q4 e

Some sample inputs: these accept:

a a b b

(the empty string)

a a a a a b b b b b

these reject:

a a a b b b b b

a a a b b

A machine that accepts any string that consists of at least one 'a' followed by at least as many 'b's:

:States:
q1 q2 q3 q4
:Start State:
q1
:Accept States:
q4
:alphabet:
a b
:stack alphabet:
$ a
:rules:
q3 b e q3 e
q3 b a q3 e
q2 b a q3 e
q2 a e q2 a
q1 e e q2 $
q3 e $ q4 e

Some sample inputs: these accept:

a b

a a a b b b b b b b

these reject:

(the empty string)

a a a b b

back