| Autor |
Beitrag |
    
Gucci
| | Veröffentlicht am Sonntag, den 29. April, 2001 - 21:33: | 
|
Ich komme leider mit einem Problem über definite Sprachen nicht recht weiter, sollte jemand von Euch auf dem Gebiet der Theoretischen Informatik beschlagen sein kann er mir ja vielleicht helfen.
Eine Sprache L element aus Sigma* heißt definit, falls es ein k element aus N gibt, sodaß die Entscheidung ob ein w element aus L oder w nicht elementaus L nur von den (maximal) k letzten Zeichen w(Index[n-k+1])....w(Index[n]) des Wortes w = w1.....wn abhängt.
a.) Geben Sie eine formale Definition einer definiten Sprache an.
b.) Zeigen Sie, daß jede definite Sprache regulär ist.
Vielen Dank schon mal im voraus,
C. Gucci. |
Michael
| | Veröffentlicht am Mittwoch, den 09. Mai, 2001 - 01:11: |
|
Hi!
Ich möchte hier wieder mal eine Lösung im Namen von SpockGeiger posten. Vielen Dank für die Erklärungen und da wir noch ein paar Aufgaben vor uns haben hoffen wir uns vielleicht noch den einen oder anderen Tip von Dir einholen zu können.
Beweis der Aufgabenstellung:
a) Eine Sprache ist L definit <=> es existiert k aus N, sodass (|w|>=k =>
(für alle x aus Sigma* ist w aus L <=>xw aus L)
b) Sei ein solches k gegeben, d.h. für jedes Wort w aus L ist w aus L <=>
die letzten k Zeichen von w sind in L.
D.h. wir können die folgende Sprache betrachten: S:={w: |w|=k und w aus L}.
S ist Teilmenge von L. Die Elemente dieser Sprache sind gerade die Endungen
erlaubter Wörter, und wenn wir ein bel. Wort an ein Wort aus S dranhängen,
so bleiben wir in L, und andersherum; wenn wir ein Wort mit Länge mindestens
k aus L nehmen, so liegt seine Endung (die letzten k Buchstaben als Wort
betrachtet) in S. Nun könnte es noch Worte in L geben, die kürzer als k
sind, die packen wir einfach in eine dritte Sprache T:={w aus L mit |w|<k}.
Wenn wir die Konkatenation von Sprachen AB:={ab mit a aus A und b aus B}
betrachten, so ist nach dem, was wir bisher festgestellt haben:
L=(Sigma*S)vereinigt T
Nun ist aber Sigma* sowas von regulär, und S und T sind als endliche Mengen
auch regulär. Und da reguläre Sprachen unter Konkatenation, Vereinigung (und
Durchschnit, Komplement und noch weiterem) abgeschlossen sind, ist L
regulär.
Danke,
Michael u. Christoph |
|
