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

Informatiker Board » Themengebiete » Theoretische Informatik » Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Gunther
Grünschnabel

Dabei seit: 08.11.2011
Beiträge: 2

Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!

Zitatantwort auf diesen Beitrag erstellen

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 19:49

Nehmen Sie Gunther in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Karlito: 08.11.2011 22:04.

08.11.2011 22:01

Nehmen Sie Karlito in Ihre Freundesliste auf

Gunther
Grünschnabel

Dabei seit: 08.11.2011
Beiträge: 2

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Gunther: 08.11.2011 22:23.

08.11.2011 22:21

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

08.11.2011 23:11

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Formale Sprachen: Bitte um Hilfe bei einer Aufgabe!