鉴于常规语言，找到正则表达式

Question

语言是如下。

Σ= {A，B，C}

L =在第二和第三对ω的最后一个字符是相同的，ω具有长度大于5和ω包含CCC。

我想这样做，我不知道这是否是正确的。得到如下：

（（CCC）（aUbUc）*（A）（A）（aUbUC））U（（CCC）（aUbUc）*（B）（B）（aUbUC））U（（CCC）（aUbUc）*（C）（ C）（aUbUC））

这个对吗？

Answer 1

不，这是不正确的。例如，你的表达不能识别字符串aaccc，因为所有的子表达式的要求，你的字符串开始ccc，这是什么样的语言描述将表明不同。

有些你表达的是对的，如需要打出的aa，bb和cc部分。你是过度使用括号一点，但是这只是一个口味，而不是正确的事情。

你的基本单位是(aUbUc)，代表∑。字符串必须包含的某个地方在ccc了，所以让我们开始只是：

(aUbUc)*ccc(aUbUc)*

这是一个包含ccc所有字符串。第二个要求是复杂的：第三，从倒数和第二从 - 最后一个字符必须是相同的。这可能与ccc部分重叠。如果没有，这就足够了：

(aUbUc)*ccc(aUbUc)*(aaUbbUcc)(aUbUc)

但是，这并不能让我们有一个像accca或aaccc的字符串。请注意，但是，它确实需要所有字符串至少为长度为6，所以它满足的字符串长度要大于5我要和缩写，而不是使用∑ (aUbUc)更高的要求，使这个小：

(∑*ccc∑*(aaUbbUcc)∑)U(∑∑∑∑*ccc)U(∑∑∑*ccc∑)

注意额外的∑s，这都需要垫出其它的子表达式，以确保所有的路径具有字符串长度大于5。

要拿出一个正则表达式另一种是直接建立一个DFA，这种语言相匹配，然后convert it to a regular expression。构建DFA时，如需要，以确保您覆盖的重叠情况，其中ccc靠近字符串的结尾，你会发现类似的担忧。为了使这更容易一点，你可以用NFA开始，然后转换您的NFA为DFA。