L={wxw^R| w, x 属于 {a,b}^+ } 是正则语言。在书中，他们通过将其转换为正则表达式 a(a+b)^+a + b(a+b)^+b 来使其成为正则，这显然是一个以相同开头和结尾的表达式现在，通过这样做 w=ab x=a wr=ba 将被接受，并且 wxwr 生成的每个字符串都将被接受，但不在 wxwr 中的字符串也将被接受，如 w=abb x=ab wr=bbaaaaaa 也将被接受。当我们无法构造有限自动机时，这到底是一种常规语言吗？很困惑
最佳答案
but the strings which are not in wxwr will also be accepted like w=abb x=ab wr=bbaaaaaa will also be accepted.
正则表达式 a(a+b)^+a + b(a+b)^+b 确实接受字符串 wxw^r = (abb)(ab)( bbaaaaaa) 因为它可以解释为字符串 wxw^r = (a)(bbabbbaaaaa)(a)。该语言未指定如何拆分 w、x 和 w^r 之间的符号接受以强制 w 和 w^r 被颠倒。对于您建议的解析，我们不满足该条件，但对于我的解析，我们满足。正则表达式起作用的原因是，只要单词以相同的符号开头和结尾，我们总是可以将 w 作为第一个符号，w^r成为最后一个，x 成为其他一切。这个选项对我们开放，我们每次都可以自由选择。
我们绝对可以为正则表达式制作一个 DFA。 NFA 特别容易制作。
关于regular-language - 如何L={wxw^R| w, x 属于 {a,b}^+ } 是正则语言，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36906176/