Sample LBA Inputs

These examples are for use with the perl LBA emulator provided at the bottom of Context Sensitive Languages. That page also contains a description of what a LBA is and how it works.

This machine accepts strings of the form $\{a^{n}b^{n}c^{n}d^{n}|n\geq 0\}$ .
Note that in this example, the input must be bounded by one "_" on each side as a tape delimiter.

:States:
start findA findB findC findD reset halt
:Start State:
start
:Accept States:
halt
:alphabet:
_ a b c d $
:tape bound:
1 0
:rules:
start     _     findA     _     right
findA     $     findA     $     right
findA     a     findB     $     right
findA     _     halt      _     left
findB     $     findB     $     right
findB     a     findB     a     right
findB     b     findC     $     right
findC     $     findC     $     right
findC     b     findC     b     right
findC     c     findD     $     right
findD     $     findD     $     right
findD     c     findD     c     right
findD     d     reset     $     left
reset     $     reset     $     left
reset     a     reset     a     left
reset     b     reset     b     left
reset     c     reset     c     left
reset     d     reset     d     left
reset     _     findA     _     right

Some sample inputs:
These accept:

_ a a a b b b c c c d d d _

_ _

_ a b c d _

These reject:

_ a a a b b b c c d d d _

_ a c _

_ a b b c c d d _

back