| |
| Autor |
  Konkatenation regulärer Sprachen |
|
aequivalenzklasse
Aktiv 
Dabei seit: 04.01.2023
Mitteilungen: 30
 |  Themenstart: 2023-09-28
|
Guten Abend zusammen,
bedauerlicherweise stehe ich auf dem Schlauch. Es geht um die Konkatenation zweier regulärer Sprachen. Seien \(L_1 = \{a^n | n\geq0\}, L_1 = \{b^n | n\geq0\}\). Dass die beiden Sprachen regulär sind, liegt auf der Hand – es ist nicht schwer einen DEA oder entsprechende reguläre Ausdrücke zu finden. Wieso ist aber die Konkatenation in diesem Falle unzulässig? Zumindest sollen wir den "Denkfehler" in einer Aufgabe identifizieren.
Denn \(L_1L_2 = \{a^nb^n|n\geq0\}\) ist ja kontextfrei. Liegt es an den Exponenten oder worauf will das Übungsblatt hinaus? Eigentlich sind ja die beiden \(n\) jeweils unterschiedliche, d.h. es müsste \(L_1L_2 = \{a^{n}b^m|n\geq0,m\geq0\} = \{\lambda, a, b, ab, aab, abb, aabb, ...\} \neq \{\lambda, ab, aabb\}\) sein, oder?
Vielen Dank und Grüße
|
 Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1778
Wohnort: Kiel, Deutschland
 |  Beitrag No.1, eingetragen 2023-09-28
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-09-28 00:42 - aequivalenzklasse im Themenstart)
Guten Abend zusammen,
Seien \(L_1 = \{a^n | n\geq0\}, L_1 = \{b^n | n\geq0\}\). Dass die beiden Sprachen regulär sind, liegt auf der Hand – es ist nicht schwer einen DEA oder entsprechende reguläre Ausdrücke zu finden. Wieso ist aber die Konkatenation in diesem Falle unzulässig?
\quoteoff
Warum sollte es nicht zulässig sein, die beiden Sprachen zu konkatenieren?
\quoteon Denn \(L_1L_2 = \{a^nb^n|n\geq0\}\) ist ja kontextfrei.
\quoteoff
Zwar ist \(\{a^nb^n|n\geq0\}\) kontextfrei, aber diese Sprache ist nicht gleich \(L_1L_2\).
\quoteon Eigentlich sind ja die beiden n jeweils unterschiedliche, d.h. es müsste \(L_1L_2 = \{a^{n}b^m|n\geq0,m\geq0\} = \{\lambda, a, b, ab, aab, abb, aabb, ...\}\) sein?
\quoteoff
Das stimmt.
Formuliere die Aufgabe also noch einmal sauber neu, oder zitiere besser noch den Originalwortlaut der Aufgabe.
mfg
thureduehrsen
\(\endgroup\)
|
Profil
|
aequivalenzklasse
Aktiv
Dabei seit: 04.01.2023
Mitteilungen: 30
| Beitrag No.2, vom Themenstarter, eingetragen 2023-09-28
|
Hallo,
Danke für Deine Antwort! Der Originalwortlaut der Aufgabe lautet:
Finden Sie den Fehler in folgender Argumentation und begründen Sie, warum diese fehlerhaft ist:
\(A=\{a^n|n\geq1\}\) ist regulär, genauso \(B=\{b^n|n\geq1\}\)
Mit den Abschlusseigenschaften regulärer Sprachen gilt nun, dass die Konkatenation \(AB\) ebenfalls regulär ist, also gilt \(\{a^nb^n | n \geq 1\} ∈ REG\).
Im Grunde ging es mir nur um die Versicherung, dass ich alle Aspekte beachtet habe bei meiner Erklärung des Argumentationsfehlers, da ich im ersten Moment verwirrt war, da ja \(a^nb^n\) nicht regulär ist.
Viele Grüße
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1778
Wohnort: Kiel, Deutschland
| Beitrag No.3, eingetragen 2023-09-29
|
Das hier ist (wie so ziemlich alles in der Mathematik) eine Übung im genauen Hinsehen und exakten Formulieren.
Schreibe mal deine Lösung hier auf, dann können wir prüfen, ob sie wasserdicht ist.
Insbesnondere würde ich gerne sehen, wie du den Argumentationsfehler in der Aufgabe identifizierst.
mfg
thureduehrsen
|
Profil
|
aequivalenzklasse
Aktiv
Dabei seit: 04.01.2023
Mitteilungen: 30
| Beitrag No.4, vom Themenstarter, eingetragen 2023-09-30
|
Vorneweg: In der Aufgabenstellung hieß die zweite Sprache B und nicht (ebenfalls) A, das habe ich korrigiert und war ein Tippfehler.
Beide Sprachen \(A\) und \(B\) sind regulär. Damit gilt nach den Abschlusseigenschaften für reguläre Sprachen, dass auch die Konkatenation \(AB\) regulär ist.
Der Argumentationsfehler liegt darin, dass die beiden Indices der Sprachen \(A\) und \(B\) logisch verschieden, aber gleich in der Benennung, nämlich \(n\), sind. Hierauf muss bei der Konkatenation der Sprachen geachtet werden. Daher ist
\(AB = \{a^n b^m \ | \ n, m \geq 0\} = \{\lambda, a, b, aa, bb, ab, aab, abb, ...\} \neq \{a^n b^m \ | \ n, m \geq 0 \ \text{mit} \ n=m\} = \{a^n b^n \ | \ n\geq 0\} = \{\lambda, ab, aabb, aaabbb, ... \}\)
Dies wäre zudem auch ein Widerspruch zu der Tatsache, dass \(\{a^n b^n \ | \ n \geq 0\}\not\in REG\) ist (was mit dem Pumping-Lemma an dieser Stelle einfach bewiesen werden könnte, was hier aber vorausgesetzt wird, da es quasi Vorwissen für die Aufgabe ist).
|
Profil
| | Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen. |
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1778
Wohnort: Kiel, Deutschland
|  Beitrag No.5, eingetragen 2023-10-01
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Das gefällt mir sehr gut. 👍
Einziger Schönheitsfehler ist, dass das \(n\) in \(a^n\) kein Index, sondern ein Exponent ist.
\quoteon(2023-09-30 23:26 - aequivalenzklasse in Beitrag No. 4)
Vorneweg: In der Aufgabenstellung hieß die zweite Sprache B und nicht (ebenfalls) A, das habe ich korrigiert und war ein Tippfehler.
[...] dass die beiden Indices der Sprachen \(A\) und \(B\) logisch verschieden, aber gleich in der Benennung, nämlich \(n\), sind.
\quoteoff
Ich weise darauf insbesondere hin, weil hier eine Verwechslungsgefahr mit dem Index der Nerode-Relation besteht.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
