Unterschied zwischen regulärem Ausdruck und Grammatik in Automaten

Ich bin neu in Automaten und habe erst gestern eine kurze Einführung in reguläre Ausdrücke erhalten. Ich habe die verschiedenen Regeln gelesen, um einen regulären Ausdruck zu definieren. Ich kann jedoch nicht zwischen regulären Ausdrücken und der Grammatik einer Sprache unterscheiden (mir wurde die Grammatik für reguläre Ausdrücke nicht beigebracht).

Ich verstehe, dass Grammatik uns hilft, die gültigen Zeichenfolgen in einer Sprache zu generieren, aber das ist es, was die Regeln zum Definieren eines regulären Ausdrucks angeben. Wo liegt also der Unterschied? Ich fragte meinen Professor und er sagte, dass Regex die grundlegendsten Zeichenketten in einer Sprache sind und dass Grammatik das Regelwerk für jede Sprache ist, die von höherer Ordnung ist als Regex. Kann jemand etwas ausführlichere Informationen liefern?

Reguläre Ausdrücke, reguläre Grammatiken und endliche Automaten sind einfach drei verschiedene Formalismen für dieselbe Sache. Es gibt Algorithmen, die von einem in einen anderen konvertiert werden können.

Der Grund, warum wir alle drei haben, ist, dass sie unabhängig voneinander erstellt wurden, wobei die ersten Äquivalenzen (es gibt auch mehrere andere Formalismen) von Kleene bewiesen wurden (dieses Ergebnis oder ein Teil davon wird Kleenes Theorem genannt).

In diesem Kontext erkennen oder generieren alle Modelle Zeichenfolgen einer regulären Sprache, je nachdem, in welcher Richtung Sie die Modelle ausführen möchten, und mathematisch besteht in diesem Sinne kein Unterschied.

Natürlich ist manchmal ein Modell aufgrund der Details des Formalismus für eine bestimmte Aufgabe einfacher zu verwenden als ein anderes. Darüber hinaus ist die Art und Weise, wie sie im Kopf eines Menschen arbeiten, oft etwas anders. Endliche Automaten "fühlen" sich wie Computer, reguläre Ausdrücke "fühlen" sich wie eine Zeichenkette aus kleineren Teilzeichenfolgen und reguläre Grammatiken "fühlen" sich wie eine traditionellere Grammatik Ableitung oder Klassifizierung eines Satzes in einer Sprache (nicht überraschend, wenn man sich die Geschichte ansieht).

Um die beiden zu vergleichen, definieren wir sie:

Reguläre Ausdrücke

So werden reguläre Ausdrücke wie folgt rekursiv definiert:

1. ist ein regulärer Ausdruck$\emptyset$
2. ist ein regulärer Ausdruck$\varepsilon$
3. ist ein regulärer Ausdruck für jeden ein & egr ; $a$$a \in \Sigma$
4. $A$$B$
   • $A\cdot B$
   • $A \mid B$
   • $A^{\ast}$

Zusammen mit einer gewissen Semantik (dh wie wir die Operatoren interpretieren, um eine Zeichenfolge zu erhalten) erhalten wir eine Möglichkeit, Zeichenfolgen aus einer regulären Sprache zu generieren.

Regelmäßige Grammatiken

$(N,\Sigma, P, S \in N)$$N$$\Sigma$$S$$P$$\Sigma^{\ast}$$P$

Rechte lineare Grammatik

$B$$C$$a$$\varepsilon$

1. $B \rightarrow a$
2. $B \rightarrow aC$
3. $B \rightarrow \varepsilon$

Linke lineare Grammatiken

$B \rightarrow Ca$

Dinge zum Nachdenken

Wenn wir uns diese Definitionen ansehen und mit ihnen spielen, können wir sehen, dass reguläre Ausdrücke wie übereinstimmende Regeln aussehen oder wie man ein bisschen mit Strings umgeht.

$S$

Diese tun jedoch genau dasselbe, und wie Sie die Metapher ihrer Funktion sehen, liegt ganz bei Ihnen.