Wird als reguläre Sprache klassifiziert?

7

Wird als reguläre Sprache klassifiziert?L={ab}

Ich bin verwirrt, weil ich weiß, dass nicht regulär ist. Welchen Unterschied macht der Kleene-Stern?L={anbn}

user6268553
quelle
3
Sie müssen angeben, dass n eine freie Variable ist. es sieht aus wie eine Konstante in deinem Ausdruck, die mich verwirrt hat.
user541686

Antworten:

19

Eine Sprache ist per Definition regulär, wenn sie von einem DFA akzeptiert wird. (Dies ist mindestens eine gebräuchliche Definition.) Können Sie sich vorstellen, dass ein EDA die Sprache akzeptiert?

Ein bekanntes Ergebnis (das in vielen Lehrbüchern bewiesen ist) besagt, dass die Sprache eines regulären Ausdrucks regulär ist. Da ein regulärer Ausdruck ist, muss seine Sprache regulär sein (wenn Sie diesem Ergebnis glauben).ab

Schließlich Ihre Frage zu beantworten (was für einen Unterschied macht die Kleene Stern make): in der Sprache , müssen wir zählen die Anzahl der s und s; in der Sprache tun wir das nicht.{anbn:n0}abab

Yuval Filmus
quelle
1
Der reguläre Ausdruck in der realen Welt ist alles andere als regulär. nikic.github.io/2012/06/15/…
Guilherme Bernal
7
@ GuilhermeBernal Das stimmt. Leider wird der Ausdruck "regulärer Ausdruck" verwendet, um beide Arten zu bezeichnen. In meiner Antwort ist ein regulärer Ausdruck das in der formalen Sprachtheorie definierte Konzept.
Yuval Filmus
@ GuilhermeBernal: POSIX ERE ist regelmäßig. Es sind nur BRE, PCRE und andere verrückte Sachen, die es nicht sind.
R .. GitHub STOP HELPING ICE
14

{ab} ist eine reguläre Sprache, da sie durch einen regulären Ausdruck generiert wird.

Der Hauptunterschied zwischen und besteht darin, dass Zählen der und erfordert , um zu überprüfen, ob es dasselbe gibt Anzahl von ihnen, während keine Zählung erfordert. Das Zählen erfordert unbegrenzten Speicher, wenn die Anzahl größer wird, aber endliche Automaten haben nur eine begrenzte Menge an Speicher, so dass ein endlicher Automat nicht erkennen kann . Andererseits kann ein endlicher Automat da dies lediglich die Überprüfung erfordert, ob das (eine beliebige Zahl) vor dem (eine beliebige Zahl) steht.L={ab}L=={anbn}L=abLL=Lab

Aus diesem Grund definiert der Kleene-Stern keine Sprachen, für deren Erkennung unbegrenztes Gedächtnis erforderlich ist. Er bedeutet „beliebige Zahl“, und jedes Mal, wenn der Stern angetroffen wird, kann die Zahl unterschiedlich sein.

Gilles 'SO - hör auf böse zu sein'
quelle
Ich danke dir sehr. Das hat mir wirklich den Unterschied erklärt!
user6268553
"Benötigt unbegrenztes Gedächtnis" ist eine gute intuitive Art, darüber nachzudenken, aber das Pump-Lemma ist, wie Sie tatsächlich beweisen würden, dass es nicht regelmäßig ist.
R .. GitHub STOP HELPING ICE
0

Jede Sprache, für die Sie ein DFA entwickeln können.

Überprüfen Sie einfach, ob Sie für beide Sprachen einen DFA zeichnen können.

L1=ab

x bezeichnen alle Vorkommen des Alphabetsx

Zeichenfolgen: , a, b, aa, ab, bb, ..ϵ

Geben Sie hier die Bildbeschreibung ein

Um einen Satz von Zeichenfolgen zu generieren, die zu , muss die Maschine die Anzahl der a und b nicht verfolgen. Da sich FA nur an das zuletzt verarbeitete Alphabet erinnern kann, kann DFA entwickelt werden.L1

DFA existieren.

Deshalb regelmäßig.

L2=anbn

Zeichenfolgen: , aa, bb, aaa, bbb, ..ϵ

Um einen Satz von Zeichenfolgen zu , die zu , muss die Maschine die Anzahl der gedruckten a verfolgen, um die gleiche Anzahl von b zu drucken. FA kann sich jedoch nur an das zuletzt verarbeitete Alphabet erinnern.L2

Um eine Maschine zu konstruieren, die akzeptiert, wir einen weiteren Speicher hinzufügen. Eine solche Maschine heißt PDA (Push Down Automate).L2

Es ist kein DFA vorhanden.

Daher nicht regelmäßig.

Alwyn Mathew
quelle