This machine accepts strings of the form {aⁿbⁿcⁿdⁿ | n≥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 _

http://cs.marlboro.edu/ courses/ fall2006/ tutorials/ chomsky_hierarchy/ Sample_LBA_inputs
last modified Sunday November 19 2006 8:42 pm EST