可计算性与复杂性/形式语言/乔姆斯基层次结构/LBA 示例输入
这些示例用于与 上下文敏感语言 底部提供的 perl LBA 模拟器一起使用。该页面还包含关于 LBA 是什么以及它是如何工作的描述。
此机器接受形式为 的字符串。
请注意，在此示例中，输入必须在两侧各用一个 "_" 作为磁带分隔符进行边界限定。
: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
一些示例输入
这些被接受
_ a a a b b b c c c d d d _
_ _
_ a b c d _
这些被拒绝
_ a a a b b b c c d d d _
_ a c _
_ a b b c c d d _