View source for Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample PDA inputs

= 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 <math>\{a^{n}b^{n}|n \ge 0\}</math>:
 :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

[[../Context Free Languages/|back]]

{{BookCat}}