关于图灵机语言L的生成规则及递归元素w'的疑问

首先要明确：你给出的语言定义存在括号歧义，结合给定答案仅允许类似babababa的字符串，推测正确的递归生成规则应该是：

L = {aba, ba} ∪ { ba + w' | w' ∈ L }
（注：原定义里的(ba | w')实际应为ba拼接w'，而非逻辑或，否则定义会陷入循环无意义）

w'的替换规则 #

w'可以替换为L中的任意字符串，包括基础串aba、ba，以及递归生成的串（比如baba、baaba等），并非只能替换为ba。

为什么无法生成abaaba？ #

因为所有递归分支都要求新生成的串必须以ba开头（除了基础串aba）：

• 基础串只有aba和ba；
• 递归生成时，只能在一个L中的串前面拼接ba，没有规则允许在aba后面拼接任何串，也没有规则允许两个aba直接拼接。
  因此abaaba（两个aba拼接）不符合任何生成规则，无法被生成。

L可生成的所有字符串 #

• 基础串：aba、ba
• 递归生成串：
  • ba + ba = baba
  • ba + aba = baaba
  • ba + baba = bababa
  • ba + baaba = babaaba
  • ba + bababa = babababa
  • 以此类推，所有串要么是单独的aba，要么是以ba开头、后面接任意L中串的字符串。

内容的提问来源于stack exchange，提问作者Silver Ms