Myhill und Nerode Regularität von Sprachen

Question

Zeigen Sie mithilfe des Satzes von Myhill und Nerode, entweder, dass die Sprache

L₂ = {x^k | k ≥ 1 ist eine Zweierpotenz} ⊆ {x}*

regulär ist oder nicht.

Answer 1

x²ⁿ⁺¹ wird durch  x^2n+1-2n-1 zu einem Wort aus L ergänzt.

x²ⁿ⁺¹⁺¹ wird durch  x^2n+2-2n+1-1 zu einem Wort aus L ergänzt.

Wegen 2ⁿ⁺¹-2ⁿ-1 < 2ⁿ⁺²-2ⁿ⁺¹-1 sind x²ⁿ⁺¹ und x²ⁿ⁺¹⁺¹ in unterschiedlichen Äquivalenzklassen bezüglich der Nerode-Relation. Per Induktion folgt, dass die Nerode-Relation unendlich viele Äquivalenzklassen hat.