string - 计算带有可选部分的字符串的所有可能性

Question

我想生成一个包含可选部分的字符串的所有可能组合的列表。这可能最好用一些例子来解释:

• A[B] → A 和 AB
• A[B][C] → A、AB、AC 和 ABC
• A[B[C]] → A、AB 和 ABC

我希望这足以解释我正在尝试做的事情。

我可以为此拼凑出我自己的小解析器或“算法”，但我有一种强烈的感觉，即有一个现有的(并且更简单的)解决方案。因为我(还)没有接受过任何类型的 CS 教育，所以我不知道我正在寻找什么样的算法，甚至不知道要使用什么搜索词。

我的直觉是否正确，是否确实存在(有据可查的)方法？

Answer 1

我还没有读过这篇文章，但似乎已经研究过这个问题。有一篇文章第 117 页:“形式语言枚举”http://www.eatcs.org/images/bulletin/beatcs89.pdf

您可以通过使用诸如“enumerate language for DFA”之类的良好关键字进行搜索来找到有关此主题的更多信息