regular-language - 是 L = {wxw| x, w ∈ {a,b}*} 一个正则语言？

Question

我需要决定语言 L = {wxw| x, w ∈ {a,b}* , w≠ε} 是否正则。

我知道 L2 = {wxw ^R | x, w ∈ {a,b}* , w≠ε} 是常规的，因为您可以确保单词以相同的字母开头和结尾，但如果没有反转，它似乎不起作用，（例如 w = 10, x = ε)

我怎么证明呢？

标签： regular-languageautomata

Answer 1

这不正常。使用 Myhill-Nerode。考虑前缀 a^n b。可以附加到此以获取该语言中的字符串的以 b 结尾的最短字符串是 a^n b。这意味着每个这样的前缀都是可区分的，并且没有 DFA。