Ist diese Sprache regulär oder nicht?

Question

Ich habe die Sprache {4^(w⋅g)34^(g)|w,g∈NAT} über dem Alphabet {0,1}.

Ich muss herausfinden, ob diese Sprache erkennbar, entscheidbar, kontextfrei, regelmäßig oder nichts davon ist.

Wie soll ich das machen bzw. wissen?

Danke

Answer 1

Betrachten Sie eine beliebige Zeichenfolge des Formulars 4^a 3 4^b.Können wir finden w, g für unser a, b?Nun, das wissen wir g muss gleich sein b, und dann können wir wählen w = a + g.Seit a, b Und g sind natürliche Zahlen und müssen es auch sein w;Die Antwort lautet: Ja, für jede Zeichenfolge dieser Form 4^a 3 4^b, wir haben eine Zeichenfolge in Ihrer Sprache.

Die Sprache aller Zeichenfolgen des Formulars 4^a 3 4^b wird durch den regulären Ausdruck beschrieben 4* 3 4* und als solche ist Ihre Sprache regelmäßig, kontextfrei, entscheidbar und erkennbar.

Angenommen, Ihre Sprache wäre nicht regelmäßig;Wie konntest du das erkennen?Sie könnten das Myhill-Nerode-Theorem oder das Pumping-Lemma für reguläre Sprachen verwenden, um einen Widerspruch aus der Annahme abzuleiten, dass die Sprache regulär sei.

Angenommen, Ihre Sprache wäre nicht kontextfrei.Sie könnten das Pumping-Lemma für kontextfreie Sprachen verwenden, um einen Widerspruch aus der Annahme abzuleiten, dass die Sprache kontextfrei sei.

Wenn Ihre Sprache nicht entscheidbar oder erkennbar wäre, könnten Sie dies natürlich auch auf verschiedene Weise beweisen.