Diskussion:Reguläre Sprache

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 7 Jahren von H.Marxen in Abschnitt Beispiel
Zur Navigation springen Zur Suche springen

Konstruktion mechanischer Geräte

[Quelltext bearbeiten]

„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)) Beantworten
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)Beantworten
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)Beantworten

Abschlusseigenschaften

[Quelltext bearbeiten]
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)Beantworten


Abschlusseigenschaften

[Quelltext bearbeiten]

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)Beantworten

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

Beispiel

[Quelltext bearbeiten]

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
  • 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)Beantworten

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)Beantworten

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 anbringen. Erhellender fände ich aber ein paar unendliche Sprachen wie . --Zahnradzacken 22:45, 30. Okt. 2011 (CET)Beantworten

Wie genau soll der endliche Automat mit nur einem Zustand aussehen, der 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)Beantworten

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)Beantworten
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)Beantworten
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)Beantworten