在单带图灵机上查找回文而不改变单词
很容易找到用(Φ)替换两端字母的回文。 ΦabaΦ ΦΦbaΦ ΦΦbaΦ ΦΦbaΦ ΦΦbaΦ ΦΦbaΦ ΦΦbΦΦ ΦΦbΦΦ ΦΦbΦΦ ΦΦΦΦΦ ΦΦΦ…
图灵机需要多少个状态来决定这种语言?
语言 L = {1^200},或者更确切地说,是连续有 200 个 1 的语言?也就是说,该 TM 仅在连续接收到 200 个“1”后才接受。因此是否需要 200 个状态来解…
最小化有限状态自动机
我正在尝试最小化此 DFA: http://img145.imageshack.us/img145/3006 /dfac.png 这是我的最小化 DFA:http://img195.imageshack。 us/img195/4131/mdf…
我说得对吗? (有限自动机)
我得到了一个正则表达式,我应该将其转换为 NFA,然后转换为 DFA。这是正则表达式: a ( b | c )* a | aac* b 然后我使用 Thomson 算法将其转换为 NFA…