正規言語

Question

は、私は、彼らが言語が

L = {WW ^Rによって表されると述べている多くのフォーラムに遭遇している| ^R W（0,1 Wの逆であり、Wが属します）^*}

は普通ではありません。そしてそれは、補題をポンピングすることによっても証明されています。

しかし、私はthisリンクに記載されているのと同じロジックを使用して、このための正規表現を書くことができます。
CHECK THIS：

（0 + 1）^* 11（0 + 1）^* +（0 + 1）^* 00（0 + 1）^*

ロジックに欠陥がありますか？それとも私が紛れているかもしれない何か。事前に 感謝:)

Answer 1

(0+1) * 11 (0+1) * + (0+1) * 00 (0+1) * + (0+1) *   initial 
= (0+1) * 11 (0+1) * + ((0+1) * 00 (0+1) * + (0+1) *)  union is associative 
= (0+1) * 11 (0+1) * + (0+1) *        L u U = U (U is universe) 
= (0+1) *             L u U = U (U is universe) 

(0+1)*で労働組合を含んでいるあなたの正規表現は、0 sおよび1秒のすべての文字列が含まれており、適切なサブセットとしてターゲット言語が含まれている言語です。あなたの言語には、ターゲット言語でない他の文字列の中に、文字列01100が含まれています。

+は結合を意味するために並置されていることを意味し、*はKleene閉包を意味することに注意してください。