Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample PDA inputs

Jump to: navigation, search

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 \ge 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