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

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

<br/><br/><br/>

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