Was ist Regelmäßigkeit?

Question

Dies ist eher eine Frage der Informatik als eine Programmierung, aber ich denke, dies ist der beste Ort von allen verwandten Seiten, um dies zu fragen.

Als ich Reguläre Ausdrücke entdeckte und den Ausdruck nachschaute, nahm ich an, dass diese Eigenschaft der "Regelmäßigkeit" sich auf die Tatsache bezieht, dass die Sprache des Ausdrucks ein definierbares Strukturmuster hat. Beim Lesen über das Thema und die Theorie dahinter habe ich jedoch gelernt, dass es Arten von Sprachen gibt, die nicht regelmäßig sind, und doch ist klar, dass ein Muster mit ihnen in Übereinstimmung gebracht werden kann. Eine solche Sprache ist (a^n) (b^n). Dies ist eindeutig ein Muster, und doch ist dies keine reguläre Sprache. Jetzt frage ich mich, was ist mit regulären Sprachen, die sie regelmäßig machen, und diese Sprache nicht?

Answer 1

Die Etymologie des Namens kommt von Kleenes Arbeit der 1950er Jahre, die reguläre Sätze mit seiner mathematischen Notation beschreibt, die für den Zweck geschaffen wird. Siehe .

Answer 2

Das Wort regular in regular expression bezieht sich auf das mathematische Konzept des regulären, nicht das englische Konzept. Genauso wie das Wort prime in der Mathematik wenig Bezug zu Prime Rindfleisch hat.

Es geerbt von CS (das ist ein Zweig der Mathematik ist) zu einem spezifischeren Konzept vorgelegt: http://en.wikipedia.org/wiki/Regular_language

Answer 3

regulärer Ausdruck nicht wirklich regelmäßig ist, ist der Name etymologisch.

Answer 4

Vielleicht kann der Wikipedia-Artikel auf regular languages es besser erklären, als wir können. Aber ich werde es versuchen.

Aus theoretischer Sicht ist eine reguläre Sprache (Menge von Strings) eine, die mit einem finite state automaton erzeugt werden kann. In der Programmiersprache bedeutet dies, dass es unter Verwendung von regular expressions generiert werden kann. Somit sind alle endlichen Sprachen (Mengen von Strings) regulär, aber es gibt einige unendliche Sprachen, wie z. B. eine Sprache, die nicht unter Verwendung von verwendet werden kann eine FSA oder reguläre Ausdrücke. Es gibt leistungsfähigere Computergeräte (wie zum Beispiel moderne Computer, die unter Verwendung von Turing Machines modelliert werden), die diese Sprachen erkennen können.

Der Grund, warum reguläre Ausdrücke so viel in Programmierung für die Suche nach Zeichenfolgen verwendet wird, ist, dass sie die große Mehrheit der Zeichenfolgen erkennen können, die für uns Programmierer wichtig sind, und gleichzeitig sehr schnell mit endlichen verwendet werden kann Automaten.

Answer 5

Intuitiv zu erklären ist Informatik ... knifflig. Ich werde es versuchen, aber denke daran, dass einiges davon "nahe genug" sein wird, aber nicht theoretisch streng.

Eine reguläre Sprache kann von einer Maschine festgelegt werden, die rechnerisch äquivalent zu einem endlichen Automaten (DFA/NDFA) ist. Ein endlicher Automat kann man sich als eine Maschine vorstellen, die rein in Zuständen arbeitet, keine Speicherung. Sie können also sehen, dass eine Maschine, die die Anzahl der a's und b's (und somit die unendliche * Speicherkapazität) zählen muss, um sie zu vergleichen, nicht regulär sein kann.

Zum Vergleich (abc) ⁿist regelmäßig, weil die Anzahl der Wiederholungen nicht relevant ist.

Für eine strengere (und entsprechend dichtere Ansicht) überprüfen Sie die wikipedia article und verbundenen Seiten.

_{* Das Unendliche spielt hier keine Rolle, aber ich erwähne es der Vollständigkeit halber. Es könnte einfacher sein, es als "glücklicherweise immer nur genug" Speicher zu betrachten.}