Reguläre und nicht reguläre Sprachen

Question

Aufgabe:

Gegeben ist die folgende Sprache :

L1 := {a^(m) | m > 0 ist eine Quadratzahl}. Zeigen Sie, dass L1 regulär bzw. nicht-regulär ist.

Hallo,

tut mir leid dass ich die Aufgabe hier so willkürlich reinstelle aber ich habe leider kein Plan wie ich die Aufgabe angehen soll. Dass ist die 1. Aufgabe von vielen auf dem Übungsblatt und ich denke wenn ich die hab und nachvollziehen kann werde ich die anderen hoffentlich irgendwie hinbekommen.

LG

Answer 1

Ganz einfach zu beantworten.

Die Grammatik einer regulären Sprache kann durch einen deterministischen endlichen Automaten dargestellt werden.

In einem DEA kann man nur anhand der Zustände "zählen". Da die Zustände endlich sind, es aber unendlich viele Möglichkeiten gibt, die gezählt werden müssen, gibt es für diese Sprache keinen DEA. Somit ist diese Sprache nicht regulär.

Beste Grüße