Formale Sprachen: Trios < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 09:43 Mo 13.02.2006 | | Autor: | mathiash |
| Aufgabe | Eine Sprachfamilie [mm] \mathcal{C}=\{L_i,i\in I\} [/mm] mit [mm] L_i\subseteq\Sigma^{\star} (\Sigma [/mm] ein endliches Alphabet)
heißt Trio, falls mindestens eines der [mm] L_i [/mm] nicht-leer ist und [mm] \mathcal{C} [/mm] abgeschlossen ist unter Schnittmengenbildung mit einer regulären Menge, inversen Homomorphismen und [mm] \epsilon-freien [/mm] Homomorphismen.
Ist [mm] \mathcal{C} [/mm] unter allen Homomorphismen abgeschlossen, so heißt [mm] \mathcal{C} [/mm] volles Trio.
(a) Zeige: Die Klasse der regulären Sprachen, die Klasse der kontextfreien Sprachen und die der rekursiv aufzählbaren Sprachen sind volle Trios.
(b) Zeige: Die Klasse der kontextsensitiven Sprachen und die Klasse der rekursiven Sprachen sind Trios, aber keine
vollen Trios.
(c) Jedes volle Trio enthält alle regulären Mengen. Jedes Trio enthält alle [mm] \epsilon-freien [/mm] regulären Mengen. |
Hallo zusammen,
hiermit startet eine Sequenz von Aufgaben zu Trios und vollen Trios, sog. abstrakten Sprachfamilien. Thematisch interessant mag dies vor allem fuer diejenigen sein, die zB gerade  einen Kurs ueber formale Sprachen belegt
haben und jetzt noch auf gepflegte Art ein bißchen weitermachen wollen.
Grundlage ist das entsprechende Kapitel aus dem Buch von Hopcroft und Ullman ''Introduction to automata theory, languages and computation''.
Einige Definitionen:
(i) [mm] \mathcal{C} [/mm] ist abgeschlossen unter Schnittmengenbildung mit regulären Sprachen genau dann, wenn
fuer jedes [mm] A\in\mathcal{C} [/mm] und jede reguläre Sprache L auch [mm] A\cap L\in\mathcal{C} [/mm] gilt.
(ii) Ein Homomorphismus (genauer: String-Homomorphismus) ist eine Abbildung
[mm] h\colon\Sigma^{\star}\to\Sigma^{\star}, [/mm] die verträglich mit der Konkatenation ist, d.h. fuer alle [mm] x,y\in\Sigma^{\star}
[/mm]
ist h(xy)=h(x)h(y).
Das heisst nichts anderes,. als dass h bereits durch die Bilder [mm] h(a),a\in\Sigma [/mm] vollstaendig bestimmt ist.
(iii) Solch ein Stringhomomorphismus h heisst [mm] \epsilon-frei, [/mm] falls fuer alle [mm] a\in\Sigma h(a)\neq\epsilon
[/mm]
gilt.
Hierbei bezeichnet [mm] \epsilon [/mm] den leeren String, also den einzigen String der Laenge 0.
(iv) [mm] \mathcal{C} [/mm] heisst abgeschlossen unter inversen Homomorphismen, falls fuer alle [mm] L\in\mathcal{C}
[/mm]
und alle String-Homomorphismen [mm] h\colon\Sigma^{\star}\to\Sigma^{\star} [/mm] auch [mm] h^{-1}(L)\in\mathcal{C} [/mm] gilt.
Entsprechend heisst [mm] \mathcal{C} [/mm] abg. unter Homomorphismen, falls fuer alle Homomorphismen h und alle
[mm] L\in\mathcal{C} [/mm] auch [mm] h(L)\in\mathcal{C} [/mm] gilt.
Viel Spass beim Bearbeiten.
Gruss,
Mathias
|
|
|
