图灵机语言

Question

也许有人可以解决这个问题：

当给定语言 L 时，其定义为：

L := {w ϵ {a,b}* : w=(aba | ba | (ba | w'))，其中 w' ϵ L}

这种语言能创造出什么样的词？特别是如果看着 w'。

w' 是否表示可以用 aba 或 ba 替换，还是只能用 (ba | w') 部分内的 ba 替换？

最小的单词显然是 aba 和 ba，但是一旦我到达 w' 部分，我不确定它在那里能做什么。

要明确的是，我的第一个直觉是 w' 可以递归地写入/读取 ba 和 aba，但显然（当采用给定的解决方案时）它应该只允许 babababa 等等...为什么不 abaaba...？

Answer 1

制作

w=(aba | ba | (ba | w'))

可以扩展到以下选择：

• w = aba
• w = ba
• w = w'（这又是该语言中的一个单词）

有了这些产生式规则，就不会有无限递归了。

如果

ba

和

w'

之间没有管道符号，那么您可以构建无限长的重复

ba

链。但请注意，即使如此，这么长的单词也永远不能以

a

开头，因为创建

aba

的产生式不允许之后有任何重复。