formale Sprachen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Die Operation min: [mm] $\mathcal{P}(\Sigma)^\star \to \mathcal{P}(\Sigma)^\star$ [/mm] sei definiert durch min(L) $= [mm] \{w \in L | \forall u,v \in \Sigma^\star$ mit $ w = uv, |u| \geq 1, |v| \geq 1: u \notin L \}$.
[/mm]
min beinhaltet also alle diejenigen Wörter ausL, deren echte Präfixe nicht in L liegen. Sei nun L eine reguläre Sprache, ist dann auch min(L) regulär?
Begründen Sie ihre Antwort! |
Könnt ihr mir da ein bisschen weiterhelfen? Was ich mir so schon mal zusammengesucht hab ist, dass evtl. gelten muss:
Sei A der Automat der L erkennt.
Sei B der Automat A bei dem alle Zustände (außer dem Fehlerzustand) akzeptierend sind.
Dann ist B geschnitten negiert(A) der gesuchte Automat.
Ich weiß aber damit jetzt auch nicht mehr anzufangen... Insbesondere hakts da jetzt an der formalen Ausführung...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:21 Mo 06.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
