Abgeschl. unter Schnitt < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:10 Mi 03.05.2006 | | Autor: | dobberph |
| Aufgabe | | Zeigen Sie, dass die Klasse der regulären Sprachen abgeschlossen ist unter Schnittbildung, d.h. [mm] L_{1} \cap L_{2} [/mm] ist regulär, falls [mm] L_{1} [/mm] und [mm] L_{2} [/mm] regulär sind. |
Ansatz:
Annahme: Zu jeder endlichen Sprache exisitert ein endlicher Automat.
Ich suche also hier auch eine Automatenregel, die einen Schnitt zweier Sprachen konstruiert.
- nacheinander schalten funktioniert nicht
- aber abfragen ob er bei beiden Automaten akzeptiert geht auch nicht...
Vielleicht muss man die Zustände der Automaten irgendwie miteinander verknüpfen, aber da fällt mir partout nichts ein.
Danke,
DerTobi
|
|
| |
|
Hallo Tobi,
falls [mm] S_1 [/mm] und [mm] S_2 [/mm] die Zustandsmengen der beiden Automaten sind, so probier doch mal,
S= [mm] S_1\times S_2 [/mm]
zu wählen und die beiden Automaten auf der Eingabe parallel zu simulieren. 
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:44 So 07.05.2006 | | Autor: | dobberph |
(Sry, dass ich mich so spät erst melde, war im Kurzurlaub)
Hm,
und wie kann ich 2 Automaten parallel organisieren, bzw. was heisst
S1 x S2 ?
Das kenn ich noch nicht.
Mfg,
DerTobi
|
|
|
| |
|
Hallo und guten Morgen,
[mm] S_1\times S_2 =\{(s,s')|s\in S_1,\: s'\in S_2\}
[/mm]
ist das kartesische Produkt der beiden Mengen, und die Übergangsfunktion [mm] \delta [/mm] ist dann definiert als
[mm] \delta ((s,s'),a)\:\: =\:\: (\delta_1(s,a),\: \delta_2 [/mm] (s',a))
für [mm] s\in S_1, s'\in S_2, a\in [/mm] Sigma (Alphabet).
Versuch Dir nun mal zu überlegen, wie ''der Rest des Automaten'' definiert ist.
Gruss,
Mathias
|
|
|
|
