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

From Wikibooks, open books for an open world
Jump to: navigation, search

Sample PDA Inputs[edit]

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