0 Daumen
29 Aufrufe

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

von

1 Antwort

0 Daumen
 
Beste Antwort

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

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...