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 ${\displaystyle \{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