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 . 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