Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!

08.11.2011, 19:49	Auf diesen Beitrag antworten »
Gunther	Formale Sprachen: Bitte um Hilfe bei einer Aufgabe! Hi, studiere Informatik und soll auf einem Übungsblatt unter anderem folgende Aufgabe lösen: Allerdings habe ich überhaupt keine Ahnung, wie ich z.B. bei Aufg. a vorgehen soll. Was ist denn bitte (bei der Sprache L1) {a}L1 ? Und wie sieht das mit den "Rechenregeln" aus, betrachtet man immer zuerst die Vereinigung und dann das oder umgekehrt? Ich verzweifel noch :?


08.11.2011, 22:01	Auf diesen Beitrag antworten »
Karlito	Hi, der Punkt in $[latex]\{a\}\cdot L_1[/latex]$ bedeutet Konkatenation. Also das aneinanderhängen von Zeichen. Das $[latex]\{\epsilon\}[/latex]$ stellt die leere Zeichenfolge dar. Eine Konkatenation einer Zeichenfolge mit $[latex]\{\epsilon\}[/latex]$ ergibt die selbe Zeichenfolge. $[latex] L_1 = \{\epsilon\} \cup L_1 \cdot \{a\} [/latex]$ Wäre also eine Sprache in der das leere Wort vorkommt und die Wörter mit beliebig vielen as (quasi rekursiv definiert). Die Vereinigung ist also schwächer als die Konkatenation. Das sollte zumindest das Handwerkszeug für die Bearbeitung der Aufgabe liefern. Wenn noch Unklarheiten sind, immer her damit. VG, Karlito
08.11.2011, 22:21	Auf diesen Beitrag antworten »
Gunther	Hi, vielen Dank erstmal für die Antwort! Ich verstehe allerdings noch nicht so wirklich, für was jetzt "L1" genau steht. Wenn die Sprache z.B. folgendermaßen definiert wäre: {a,b}{aa}{b} wüsste ich, was zu tun ist um zu entscheiden, ob die Wörter in der Sprache enthalten sind oder nicht. Mich verwirren bloß die ganzen "L1" in der Definition von "L1=". Kann ich denn die Definition von L1 irgendwie umschreiben, sodass ich die mir bekannte Definition erhalte? Weiß nicht ob ich dass jetzt einigermaßen verständlich rüberbringen konnte
08.11.2011, 23:11	Auf diesen Beitrag antworten »
Karlito	Hallo, L1 ist die Sprache selbst. Dadurch, dass die Sprache in ihrer definition sich selbst immer wieder Verwendet, umfasst sie unendlich viele Wörter. An meinem Beispiel $[latex] L_1 = \{\epsilon\} \cup L_1 \cdot \{a\} [/latex]$ : Verwendest du die 2. Menge $[latex] L_1 \cdot \{a\} [/latex]$ kannst du für L1 wieder die Definition einsetzen. Also $[latex] L_1 = \underbrace{( \{\epsilon\} \cup L_1 \cdot \{a\} )}_{L_1} \cdot \{a\} [/latex]$ . Wählst du jetzt epsilon, so bricht die Rekursion ab... Wählst du wieder den zweiten Term, so setzt sie sich fort und du musst wieder L1 einsetzen: $[latex] L_1 = (\underbrace{( \{\epsilon\} \cup L_1 \cdot \{a\} )}_{L_1} \cdot \{a\} ) \cdot \{a\} [/latex]$ Hoffe es wird so klarer... VG, Karlito
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »