tokenize - 如何分解字符串以检查其属于从字母表生成的语言？

Question

令 S= {a, bb, bab, abaab} 是一个字母表。并且 kleene 闭合将是 S* 将所有可能的组合。

S* 中是否存在字符串 abaabbabbaab？

什么是分解以检查它是否在 S* 中的方法？我已经通过以下方式完成了可能的分解：

1. (abaab)(bab)(b)(a)(a)(b)
2. (abaab)(bab)(b)(aa)(b)
3. (abaab)(bab)(ba)(ab)
4. (abaab)(bab)(咩)(b)
5. (abaab)(bab)(b)(aab)

我们可以看到 (abaab)(bab) 是匹配的，但后面的部分不匹配 S* 中的意志组合。我已经以多种方式分解了后面的部分，但仍然不匹配。我想问那个，

• 这是对的吗？

• 这是分解（标记）字符串的正确方法吗？

• 所有分解对都正确吗？

• 这是检查字符串是否属于一种语言的正确方法吗？

Answer 1

您的一些因式分解包含 $(b)$，它不在 $S$ 中。所以他们是不正确的。

我认为您的方法是详尽的反复试验。如果您正确地执行此操作，那么这是找到分解的正确方法。为了检查语言的成员资格，如果该语言以有限语言的 Kleene 闭包的形式给出，则它可以工作。