解決方法がわからない問題がいくつかあります。同値関係は、再帰的、対称的、反対称的、および推移的なプロパティに対応する関係セットであることを知っています。
1) アルファベット Σ = {a,b} を考えます。同値関係 RI がちょうど 1 つの同値類をもつ言語 L は?
2) L をアルファベット上の言語 (必ずしも正規ではない) とする。空文字列 [ε] を含む同値類が {ε} でない場合、それは無限であることを示してください。
3) L = {x ∈ Σ: |na(x) = nb(x)} と記述されるアルファベット Σ = {a,b} 上の言語 L を考えます。na(x) = a'sin x の数を思い出してください。
(1) na(x) - nb(x) = na(y) - nb(y) ならば xRIy であることを示せ。
(2) na(x) - nb(x) = na(y) - nb(y) でない場合、x と y は L 識別可能であることを示します。
(3) RI の等価クラスをすべて記述してください。