Präfix von REG < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 12:08 Mo 01.12.2008 | | Autor: | frankina |
| Aufgabe | Für eine Sprache L seien
min(L) = {x [mm] \in [/mm] L | kein echtes Präfix von x ist in L}
und
max(L) = {x [mm] \in [/mm] L | x ist kein echtes Präfix eines Wortes y [mm] \in [/mm] L}.
min(L) = max(L) impliziert die Gleichheit min(L) = L.
(a) Gilt auch die Umkehrung? Begründen Sie.
(b) Zeigen Sie, dass REG unter dem max-Operator abgeschlossen ist |
Mein Problem ist, das ich gar nicht wirklich weiß was min und max bedeuten.
Wodurch mir es schwer fällt besagtes zu beweisen.
Zu (a)
Ich würde sagen Nein.
Wenn min(L) = L gilt würde wenn dadurch min(L) = max(L) gilt auch max(L) = L sein.
Das geht doch nich so einfach oder??
Hm weiß nicht wie ich das begründen soll. Kann mir jemand einen Tipp geben??
Zu (b)
Um die Abgeschlossenheit zu zeigen muss man zeigen, das max für alle reguläre Sprachen gilt:
Eigentlich ist es doch klar, dass für alle Wörter y einer Regulären Sprache existiert ein x, welches kein echtes präfix von y ist.
Aber reicht das als Beweis und wie zeige ich dass das für alle regulären Sprachen gilt??
Hab halt noch große Probleme, weswegen ich mich über einen Tipp oder eine Richtigstellung meiner Aussagen sehr freuen würde!
Vielen Dank!
|
|
|
