Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Jede endliche Sprache regulär
Druckversion
Druckversion
Autor
Universität/Hochschule J Jede endliche Sprache regulär
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-18


Hallo,

ich versuche gerade einen Beweis zu verstehen.

Sei fed-Code einblenden

fed-Code einblenden

fed-Code einblenden

NFA

fed-Code einblenden

akzeptiert L.

Ich hätte dazu ein paar Fragen. Und zwar gibt es hier wirklich nur 2 Zustände, also Startzustand und Endzustand? Wenn ja wie kann ich mir das vorstellen das von diesem Automaten jedes Wort abgearbeitet werden kann?


Achja und kann es nicht endliche Sprachen geben die regulär sind?
zb: a  |  a(a|b)*a  das heißt ja dann ein Wort dieser Sprache fängt mit a an hat dann beliebig viele a's oder b's und endet mit einem a.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3165
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-18


Hallo,

ich kann deine Notation nicht lesen, aber zwei Zustände reichen natürlich nicht aus. Überlege dir selbst mal, wie ein NFA aussehen müsste, der eine Sprache erkennt, die aus nur einem Wort besteht, z.B. sei das Alphabet {0,1} und das Wort 001. Wieviele Zustände sind nötig? Kannst du den NFA nun so modifizieren, dass er eine um ein weiteres Wort, z.B. 101, ergänzte Sprache erkennt?

Die zweite Frage hast du dir anscheinend schon selbst beantwortet, oder ich verstehe sie nicht.


[Verschoben aus Forum 'Theoretische Informatik' in Forum 'Formale Sprachen & Automaten' von ligning]


-----------------
⊗ ⊗ ⊗



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-18


Danke für deine Antwort! Der Beweis steht für das Theorem genau so im Skript. Theorem: Jede endliche Sprache ist regulär. Hab die Notation jetzt nochmal verändert hoffe es ist jetzt besser lesbar. Das müsste mit 3 Zuständen funktionieren, für 001. Für ein weiteres Wort bräuchte man dann schon mehr.

So wie das im Skript steht heißt das nämlich für mich es gibt nur 2 Zustände und zwar start und Endzustand, also z und z'. Das verwirrt mich.
Dachte mir schon das kann nicht funktionieren. :)

Aus der Sprache a | a(a|b)*a werde ich aber nicht schlau. Das würde ja bedeuten, wenn ich beliebe viele a's und b's erzeugen dürfte wäre es ja nicht endlich?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3165
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-18


Ich meinte es eher nicht optisch, sondern vom Sinn her. Das ist a priori ein nichtssagendes Tupel mit 5 Elementen, die ich nicht zweifelsfrei zuordnen kann. Dein Prof. macht das anders als ich es kenne und als man es z.B. bei Wikipedia nachlesen kann. Vielleicht ist der Satz mit eurer Definition ja richtig?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-01-18


Also nochmal für mich zusammenfassend heißt das, es gibt z und z', wobei z und z' nicht unbedingt Start und Endzustand sein müssen. Sigma ist das Alphabet davon ist L eine Teilmenge. K sind die Übergangsrelationen, wobei hier z und z' auch nicht Start und Endzustand sein müssen, sodass mit einem Wort aus L der Endzustand erreicht wird. Und z und z' sind zugleich als Start und Endzustand definiert.

[Die Antwort wurde nach Beitrag No.2 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-01-18


Also ich denke das {z, z'} die Menge der Zustände ist, wobei eben nicht alle angeführt sind. K ist hier einfach statt delta. So ist das gemeint glaub ich. Wie würde das bei dir aussehen, ich hab nämlich das Skript(Uni Hamburg) im Internet gefunden, es ist nicht unseres. Aber es wird eben unsere Aufgabenstellung bewiesen :=)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3165
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-01-18


Doch, es sind immer alle Zustände aufgeführt. $Z := \{z,z'\}$ ist die Zustandsmenge, $\Sigma$ das Alphabet, $K$ die Übergangsrelation. Ich denke $\{z\}$ ist die Menge der Startzustände (ich kenne es nur so, dass man einen Startzustand haben kann, aber das kommt bei dem Beispiel zum Glück auf das gleiche raus), und $\{z'\}$ ist die Menge der Endzustände. Soweit so gut, das Problem ist, dass die Übergangsrelation offenbar eine Teilmenge von $Z\times\Sigma^*\times Z$ ist. Normalerweise ist es bei einem NFA $Z\times(\Sigma\cup\{\varepsilon\})\times Z$.

Ich sehe gerade keine prinzipiellen Schwierigkeiten, ganze Wörter für Übergänge zuzulassen. Das kann man, solange man bei NFAs bleibt, in eine Kette von einzelnen herkömmlichen Übergängen übersetzen, denke ich. Mit dieser Konvention benötigt man dann auch wirklich nur zwei Zustände für eine endliche Sprache.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-01-18


Ich steig noch nicht ganz durch. Jetzt würde mich interessieren wie das normal ausschauen würde, ich müsste ja auch die Übergänge definieren für die einzelnen Terminale? Zb. (q0, a, F oder irgendein zustand)

A = (Q, Sigma, Delta, q0, F)

Welche Zustände müsste ich jetzt für Q aufschreiben, da ich ja nicht weiss welche Zustände vorkommen?

Wie der Beweis dann im allgemeinen aussieht. Oder kann der Beweis von oben bleiben nur mit den Zuständen von Q und die definition der Übergangsrelation?

LG






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.12.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-01-18


Also ich glaub ich hab das jetzt verstanden.

Jede endliche Sprache ist regulär.

fed-Code einblenden

So und daher weiß ich das alle endlichen Sprachen auch regulär sind, da es so einen Automaten eben geben kann.

Mit delta wird eh schon die Übergangsrelation beschrieben. :)




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nastypasty hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]