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

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

Sample LBA Inputs[edit]

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 \ge 0\}.
Note that in this example, the input must be bounded by one "_" on each side as a tape delimiter.

start findA findB findC findD reset halt
:Start State:
:Accept States:
_ a b c d $
:tape bound:
1 0
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 _