Reguläre & nicht Reguläre Sprachen

[faDev]

Hallo Community,

kann mir jemand erklären was reguläre Sprachen und nicht reguläre Sprachen sind?
Finde Online nichts zu dem Thema ohne von Mathematischen Formeln überrannt zu werden!

Ich hoffe mir kann jemand helfen!

faDev.

[Klotzkopp]

Da das ein abstraktes Konzept aus der theoretischen Informatik ist, wird es ohne ein paar Formelzeichen kaum zu erklären sein.

Schon der Begriff "Sprache" hat nichts mit dem zu tun, was man sich umgangssprachlich darunter vorstellt.

 

Weißt du, was ein endlicher Automat ist?

[Gast RE: endlicher Automat]

vor 40 Minuten schrieb Klotzkopp:

Weißt du, was ein endlicher Automat ist?

Darüber hab ich eine gewisse Vorstellung, ja. 

[Klotzkopp]

vor 10 Minuten schrieb Gast RE: endlicher Automat:

Darüber hab ich eine gewisse Vorstellung, ja. 

Eine Sprache ist genau dann regulär, wenn es einen endlichen Automaten gibt, der die Sprache akzeptiert.

Beispiel:

Eine Sprache, deren Wörter aus beliebig vielen Wiederholungen der Abfolge ab bestehen (also ab, abab, ababab usw) ist regulär. Ein einfacher Automat mit zwei Zuständen akzeptiert alle Wörter dieser Sprache.

Eine Sprache, deren Wörter aus beliebig vielen Wiederholungen von a, gefolgt von genauso vielen Wiederholungen von b besteht (ab, aabb, aaabbb usw.), ist nicht regulär. Du kannst keinen endlichen Automaten dazu konstruieren, weil du dir beim Auswerten der b quasi "merken" müsstest, wieviele a in dem Wort waren.

[Gast halcyon]

1 hour ago, Klotzkopp said:

Eine Sprache, deren Wörter aus beliebig vielen Wiederholungen von a, gefolgt von genauso vielen Wiederholungen von b besteht (ab, aabb, aaabbb usw.), ist nicht regulär. Du kannst keinen endlichen Automaten dazu konstruieren, weil du dir beim Auswerten der b quasi "merken" müsstest, wieviele a in dem Wort waren.

Das ist nicht richtig, das ist sehr wohl eine reguläre Sprache und das kannst du ganz einfach mit einer Turing Maschine konstruieren in dem du folgende Zustände im Automaten definierst:

0. Wenn auf dem Eingabeband keine Zeichen sind, ist es die gesuchte Reguläre Sprache. Ende.
0.1 Wenn ein Zeichen vorhanden ist -> weiter bei 1.
1. Gehe nach rechts über das Eingabeband, bis du auf ein Leerzeichen triffst.
2. Gehe ein Zeichen nach Links
3. Wenn es ein b ist, Ersetze das b durch ein Leerzeichen -> weiter bei 4.
3.1 Wenn es ein a ist, ist es nicht die gesuchte reguläre Sprache. Ende
3.2. Wenn es ein Leerzeichen ist,  ist es die gesuchte reguläre Sprache. Ende.
4. Gehe ganz nach Links bis zum Leerzeichen
5. Gehe ein nach Rechts, wenn es ein a ist, ersetze a durch ein Leerzeichen. -> weiter bei 1.
5.1 Wenn es ein b ist, ist es nicht die gesuchte Reguläre Sprache. Ende
5.2 Wenn es ein Leerzeichen ist, ist es die gesuchte reguläre Sprache. Ende.

Bearbeitet 22. März 2017 von halcyon

[Klotzkopp]

 

vor 23 Minuten schrieb halcyon:

das kannst du ganz einfach mit einer Turing Maschine konstruieren

Ein endlicher Automat hat aber keine angeschlossene Turingmaschine.

[Klotzkopp]

@halcyon Ich muss das präzisieren:

Dein Automat erfordert, dass das Zeichen an der aktuellen Position der Turingmaschine Bestandteil des Eingabealphabets ist, weil deine Zustandsübergänge darauf beruhen.

Es gibt keinen endlichen Automaten, der die beschriebene Sprache über dem Alphabet (a, b) akzeptiert. 

[Gast halcyon]

1 hour ago, Klotzkopp said:

@halcyon Ich muss das präzisieren:

Dein Automat erfordert, dass das Zeichen an der aktuellen Position der Turingmaschine Bestandteil des Eingabealphabets ist, weil deine Zustandsübergänge darauf beruhen.

Mein leeres Zeichen gehört nicht zum Eingabealphabet, sondern ist einfach ein leeres Zeichen. Ein deterministischer Automat wie die Turingmaschine definiert sich auch nicht nur über sein Eingabealphabet sondern noch aus 6 weiteren Komponenten (darunter auch das leere Zeichen, die Zustände, das Bandalphabet etc.).

Siehe: https://de.wikipedia.org/wiki/Turingmaschine#Formale_Definition

Eine Turing Maschine ist ein deterministischer endlicher Automat der die Wörter deiner Beispielsprache erkennen kann. Die Turing Maschine ist übrigens auch die "Standard Referenz" eines deterministischen endlichen Automaten in der theoretischen Informatik.

Gut möglich, dass aabb usw. keine reguläre Sprache ist, dann aber nicht deswegen, weil man dazu keinen endlichen Automaten finden könnte, der diese Sprache erkennen kann. Das geht wie aufgezeigt.

 

Bearbeitet 22. März 2017 von halcyon

[Gast halcyon]

Ich habe noch mal in meinem Skript geschaut. Wir haben beide einen Fehler.

Du hast recht, es ist keine reguläre Sprache. Allerdings liegt das einzig und allein daran, dass eine reguläre Sprache keine Kontextfreie Grammatik besitzen darf. Die Argumentation des endlichen Automaten ist nicht richtig, oder wenn, dann nur zum Teil, weil ein endlicher Automat nicht nur aus Zuständen und einem Eingabealphabet bestehen muss (siehe Turing Maschine), aber könnte. Je nach dem, mit welchem Eigenschaften man den endlichen Automaten mit einem Tupel definiert.

 

[Klotzkopp]

vor 13 Stunden schrieb halcyon:

Allerdings liegt das einzig und allein daran, dass eine reguläre Sprache keine Kontextfreie Grammatik besitzen darf. 

Das ist Unsinn. Reguläre Sprachen sind eine Untermenge der kontextfreien Sprachen. Jede reguläre Grammatik ist auch kontextfrei. Meintest du, dass eine reguläre Sprache keine nicht-kontextfreie Grammatik besitzen darf?

Die beschriebene Sprache ist übrigens kontextfrei, nur eben nicht regulär.

vor 13 Stunden schrieb halcyon:

Die Argumentation des endlichen Automaten ist nicht richtig, oder wenn, dann nur zum Teil, weil ein endlicher Automat nicht nur aus Zuständen und einem Eingabealphabet bestehen muss (siehe Turing Maschine), aber könnte. Je nach dem, mit welchem Eigenschaften man den endlichen Automaten mit einem Tupel definiert.

Wenn man mit formalen Sprachen hantiert, ist es nützlich, den endlichen Automaten als Turingmaschine mit bestimmten Einschränkungen zu verstehen. 

Siehe auch hier: https://de.wikipedia.org/wiki/Chomsky-Hierarchie#.C3.9Cbersicht

Also nochmal:

Eine Sprache ist genau dann regulär, wenn es einen eine Turingmaschine gibt, die die Sprache akzeptiert, und die nur lesen und sich nur in eine Richtung bewegen kann. Letzteres nenne ich einen endlichen Automaten.