0 Daumen
262 Aufrufe

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

L2 = {xk | k ≥ 1 ist eine Zweierpotenz} ⊆ {x}*

regulär ist oder nicht.

Gefragt von

1 Antwort

+1 Punkt
 
Beste Antwort

x2n+1 wird durch  x2n+1-2n-1 zu einem Wort aus L ergänzt.

x2n+1+1 wird durch  x2n+2-2n+1-1 zu einem Wort aus L ergänzt.

Wegen 2n+1-2n-1 < 2n+2-2n+1-1 sind x2n+1 und x2n+1+1 in unterschiedlichen Äquivalenzklassen bezüglich der Nerode-Relation. Per Induktion folgt, dass die Nerode-Relation unendlich viele Äquivalenzklassen hat.

Beantwortet von

Vielen Dank.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...