Find a regular expression for this language:
L = {λ, ab, abac, abacab,abacabac, abacabacab,...}
Ok so I have been working of this problem for sometime now. So far I know that 'ab' repeats its self (ab). But I am stumped on 'ac'.... it cant be (ab)(ac)*... Any pointers would be appreciated.
I've looked at my book and there is not example that can show me how to solve this.
让我们从简化一下开始。让我们让 B 表示ab和 C 表示ac。然后你正在尝试生成字符串
λ, B, BC, BCB, BCBC, BCBCB, ...
在这种情况下，您可能希望将正则表达式分成两种情况：一种生成
λ, BC, BCBC, BCBCCBC, BCBCCBC, ...
和一个产生
B, BCB, BCBCB, BCBCB, ...
前者由正则表达式(BC)*给出，后者由正则表达式给出(BC)*B。如果将这些组合在一起，您会得到(BC)* | (BC)*B，可以将其重写为(BC)*(B | λ)。剩下要做的就是通过替换B和C withab andac` 来扩展它，它给出了生成的正则表达式
(abac)*(ab | λ)
这种观察还应该让您为该语言设计一个 DFA 或 NFA，但我将把它留作练习。:-)
希望这可以帮助！