證明 $L:=\{x\in\{a,b\}\,\,:\,\,x\ne x^R \}$ 為非正規語言.


[證明]


假令為正規. 但對任何$m\in\mathbb{N}$, 要是我們選定 \begin{align} w=a^m ba^N \in L,\notag \end{align} 其中 $N= m + m!$, 那麼一旦 $w$ 分解為$w=xyz$的型式, 且 $|xy|\leq m$ 以及 $|y|\geq 1$, 考慮字串 \begin{align} w_j := xy^j z,\notag \end{align} 其中 $j=1+\frac{m!}{|y|}$. 不難察覺它的樣是為 $a^K ba^N$. 又 $x$ 和$y$ 的樣式皆如同 $a^r$, 而 $z$ 的樣式為 $a^s ba^N$, 因此在中央的$b$左邊的$a$的個數$K$為 \begin{align} K = m-|y| + |y|\cdot j = m + m! .\notag \end{align} 這代表它是對稱型的字串, 也就不會落在集合$L$ 內. 此結果與幫浦定理矛盾.

口

return 0;