这是一种常规语言吗？
Is this a regular language?
这是初始语法：
S → ε | c | bSb | aAa
A → aSa | bAb
一些结果词是：
baabaabbbbaabaab
bcb
baabaacaabaab
bbaabcbaabb
ababbaba
bbbb
ababbcbbaba
baabcbaab
aaaacaaaa
aacaa
baaaaaacaaaaaab
bbbbaacaabbbb
abaaabbaaaba
abbbaaacaaabbba
起初我写了这个正则表达式(a|b)*c?(a|b)*但是后来我发现a和b的出现总是偶数，所以这个正则表达式是错误的。考虑到自动机不能计数，我是否可以得出语言不规则的结论？非常感谢！
这种语言不规则。您可以使用 Myhill-Nerode 定理证明同样多的内容，如下所示。考虑前缀 b^n c。可以附加到此字符串以获取语法语言字符串的最短字符串是 b^n；不能将更短的字符串附加到 b^n c 以获取该语言的字符串。想象一下语言是有规律的。然后在处理前缀 b^n c 之后，DFA 必须有一条到达长度为 n 的接受状态的最短路径。但是 n 是一个任意的自然数，DFA 必须有一些固定的常量状态。这是一个矛盾，所以我们的语言没有DFA，不是正则的。
生成常规语言的非常规语法示例如下：
S -> aSa | aS | A | e
aSSaa -> Saa
A -> AA | ASA | aSaSA
SAS -> ASASSASaaSa
这不正常，甚至不是上下文无关的。但它会生成 a a* 的所有字符串的常规语言，仅由于产生式 S -> aS | e。
这是初始语法：
S → ε | c | bSb | aAa
A → aSa | bAb
一些结果词是：
baabaabbbbaabaab
bcb
baabaacaabaab
bbaabcbaabb
ababbaba
bbbb
ababbcbbaba
baabcbaab
aaaacaaaa
aacaa
baaaaaacaaaaaab
bbbbaacaabbbb
abaaabbaaaba
abbbaaacaaabbba
起初我写了这个正则表达式(a|b)*c?(a|b)*但是后来我发现a和b的出现总是偶数，所以这个正则表达式是错误的。考虑到自动机不能计数，我是否可以得出语言不规则的结论？非常感谢！
这种语言不规则。您可以使用 Myhill-Nerode 定理证明同样多的内容，如下所示。考虑前缀 b^n c。可以附加到此字符串以获取语法语言字符串的最短字符串是 b^n；不能将更短的字符串附加到 b^n c 以获取该语言的字符串。想象一下语言是有规律的。然后在处理前缀 b^n c 之后，DFA 必须有一条到达长度为 n 的接受状态的最短路径。但是 n 是一个任意的自然数，DFA 必须有一些固定的常量状态。这是一个矛盾，所以我们的语言没有DFA，不是正则的。
生成常规语言的非常规语法示例如下：
S -> aSa | aS | A | e
aSSaa -> Saa
A -> AA | ASA | aSaSA
SAS -> ASASSASaaSa
这不正常，甚至不是上下文无关的。但它会生成 a a* 的所有字符串的常规语言，仅由于产生式 S -> aS | e。