给定正则语言，找到正则表达式
Given Regular Language, find Regular Expression
语言如下
∑={a,b,c}
L = ω的倒数第二个和倒数第三个字符相同，
ω 的长度大于 5，ω 包含 ccc。
我试过了，但不确定是否正确。得到以下内容：
((ccc)(aUbUc)*(a)(a)(aUbUC)) U ((ccc)(aUbUc)*(b)(b)(aUbUC)) U ((ccc)(aUbUc)*(c)(c)(aUbUC))
这是正确的吗？
不，那是不正确的。例如，您的表达式无法识别字符串 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。
语言如下
∑={a,b,c}
L = ω的倒数第二个和倒数第三个字符相同， ω 的长度大于 5，ω 包含 ccc。
我试过了，但不确定是否正确。得到以下内容：
((ccc)(aUbUc)*(a)(a)(aUbUC)) U ((ccc)(aUbUc)*(b)(b)(aUbUC)) U ((ccc)(aUbUc)*(c)(c)(aUbUC))
这是正确的吗？
不，那是不正确的。例如，您的表达式无法识别字符串 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。