411 REFERENCE · Wikibooks
Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample PDA inputs
Reference material by Wikibooks contributors. This retains its source identity and is not 411 news reporting.
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 :
: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