Diskussion:Reguläre Sprache

Konstruktion mechanischer Geräte

„Die Klasse der regulären Sprachen (...) hat in der Informatik sowie auch bei der Konstruktion mechanischer Geräte eine hohe praktische Bedeutung.“

Hat jemand einer Erklärung dafür, dass reguläre Sprachen eine hohe praktische Bedeutung bei der Konstruktion mechanischer Geräte haben sollen? (nicht signierter Beitrag von 87.166.187.35 (Diskussion | Beiträge) 18:45, 1. Feb. 2010 (CET))

Ich habe den Verweis auf mechanische Geräte entfernt. Es ist nicht unmittelbar klar, wie genau reguläre Sprachen zur Konstruktion mechanischer Geräte benutzt werden können; die Behauptung war unbelegt. --Sascha Brawer (Diskussion) 08:59, 15. Aug. 2012 (CEST)

Mechanisch? Die Steuerung (Mikroprogrammierung) von CPUs ist typischerweise eine Implementation eines endlichen Automaten, aber die arbeitet heute nicht mehr mechanisch. Ich wüsste auch nicht, was die Verwendung endlicher Automaten als Modell bei der Konstruktion mechanischer Geräte bringen sollte (Zustand?). Vielleicht wollte aber nur jemand ausdrücken, dass es auch in realita endliche Automaten gibt (nur sind die wohl eher nicht mechanisch). --77.187.147.45 17:07, 18. Apr. 2017 (CEST)

Abschlusseigenschaften

Reguläre Sprachen sind im Sinne der Theorie der Berechenbarkeit äquivalent zu Endlichen Automaten, aber das hat eher mathematisch-theoretische Bedeutung. Aus welcher Quelle stammt Deine Behauptung? --Mussklprozz 22:27, 1. Feb. 2010 (CET)

Abschlusseigenschaften

Der Absatz Abschlusseigenschaften klingt so als ob Reguläre Sprachen lediglich unter Vereinigung, Durchschnitt, Komplement, Konkatenation und Kleene-Stern abgeschlossen seien. Dies ist nicht der Fall, sie sind unter anderem auch unter Homomorphismus abgeschlossen. Schönen Gruß --DownAnUp 18:03, 14. Feb. 2010 (CET)

Wäre schön, für die behaupteten Abschlusseigenschaften einen Beleg anzugeben. mfg -- 130.75.120.11 12:44, 2. Dez. 2010 (CET)

Beispiel

Kann man vielleicht ein etwas konkreteres Beispiel machen?

Etwas in dieser Art:

• Die Sprache, die durch den regulären Ausdruck (ab)* beschrieben wird, ist regulär.
• L1 = {"ab", "b"} ist regulär
• $L2=\{a^{i}b^{j}|i<j\}$ ist nicht regulär

Ich weiß jedoch nicht sicher, ob die beiden regulär sind.

Muss eine reguläre Sprache unendlich viele Wörter haben? --MartinThoma 10:54, 29. Okt. 2011 (CEST)

Ein Beispiel würde dem Artikel sicherlich verständlicher machen. Deine Sprache L1, die ja "nur aus "ab" und "b" besteht, ist endlich und regulär (was deine Abschlussfrage beantwortet), die Sprache L2 ist nicht regulär (z.B. Pumping-Lemma, deterministischer endl. Automat, ich weiß nicht, ob man das hier auch so ausführlich zeigen sollte, oder auf (vollständige) Beweise in den jeweiligen Artikeln verweisen sollte (in die man diese Beispiele dann packen müsste)...). Grüße, --Maggus989 13:11, 29. Okt. 2011 (CEST)

Ich finde Beispiele auch nicht schlecht; aber was ist an den vorhandenen Beispielen so schlecht, dass "jede endliche Sprache ist regulär" überlesen wurde? Man könnte dann natürlich als Beispiel zum Beispiel $L_{1}$ anbringen. Erhellender fände ich aber ein paar unendliche Sprachen wie $\{a^{i}b^{j}|i,j\in \mathbb {N} \}$. --Zahnradzacken 22:45, 30. Okt. 2011 (CET)

Wie genau soll der endliche Automat mit nur einem Zustand aussehen, der $\{a^{i}b^{j}|i,j\in \mathbb {N} \}$ akzeptiert? Es muss doch mindestens zwischen den Zuständen "nächstes akzeptiertes Zeichen ist 'a' oder 'b' oder Ende" und "nächstes akzeptiertes Zeichen ist 'b' oder Ende" unterschieden werden -- Dust0r (Diskussion) 22:15, 9. Jun. 2017 (CEST)

Wieso „mit nur einem Zustand“? Das geht nicht, hast Du gerade begründet. Geht mit 2 Zuständen bzw. mit 3, wenn man den oft impliziten Fehler-Zustand mit kodieren will (z.B. nach "aba"). --H.Marxen (Diskussion) 16:21, 12. Jun. 2017 (CEST)

Im Abschnitt "Beispiele" der erste Punkt. Hier wird halt behauptet, dass es diesen Automaten mit nur einem Zustand gibt. -- Dust0r (Diskussion) 19:00, 12. Jun. 2017 (CEST)

Uff, das habe ich bisher überlesen. Das stimmt so nicht. Ist hier entstanden. Ich vermute, ein schlichter Irrtum: das Beispiel hat sich die IP vielleicht selber ausgedacht. Ein einziger Zustand gestattet nicht sehr viel, da bleibt nur sowas wie (a|b)* als Sprache. Mein Vorschlag: den Teil mit „nur einem Zustand“ einfach raus streichen; die Anzahl Zustände sollte hier auch besser nicht thematisiert werden. --H.Marxen (Diskussion) 19:27, 12. Jun. 2017 (CEST)