Informatiker Board | Druckvorschau: Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!

Geschrieben von Gunther am 08.11.2011 um 19:49:

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 :?

Geschrieben von Karlito am 08.11.2011 um 22:01:

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

Geschrieben von Gunther am 08.11.2011 um 22:21:

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 Augenzwinkern

Geschrieben von Karlito am 08.11.2011 um 23:11:

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