Übung zu Myhill Nerode. L= {a^p | p ist eine Primzahl}. Ich verstehe das Konzept nicht

Question

Hello Alle, diese Übung ist über Myhill Nerode. Ich verstehe das Konzept nicht

Aufgabe:

L= {a hoch p | p ist eine Primzahl}

a) Zeigen Sie, dass L einen unendlichen Index hat.

b) Besitzt L eine unendliche reguläre Teilmenge?

c) Ist L∗ regulär?

Comments

https://de.wikipedia.org/wiki/Satz_von_Myhill-Nerode

Kannst du ja schon mal studieren. Informatikantwort kann etwas dauern.

Answer 1

Hallo Saeede,

a) also erstmal musst du wissen, dass du einen endlichen Index (Myhill-Nerode) hast, wenn die Sprache regulär ist.

Jetzt müsstest du also zeigen, dass die obige Sprache nicht regulär ist. Und wenn sie nicht regulär ist, folgt automatisch, dass sie einen unendlichen Index hat.

Kleiner Tipp: Gehe davon aus, dass sie kontextfrei ist. Denn alle einelementigen kontextfreien Sprachen sind automatisch regulär. Dann musst du nur mit dem Pumping Lemma für Typ 3 zeigen, dass es dieses nicht erfüllt.

=> Die Sprache ist kontextsensitiv

c) Nein, ist sie nicht. Da die Sprache nicht regulär ist, denn wäre sie regulär wäre auch L* regulär (wegen den Abschlusseigenschaften. Sie ist aber kontextsensitiv und wegen den Abschlusseigenschaften von kontextsensitiven Sprachen auch kontextsensitiv.

Hoffe, dass es dir weiterhilft:)