Die Mathe-Redaktion - 22.02.2020 02:37 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 486 Gäste und 6 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
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: im letzten Monat
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.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2926
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]


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



  Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: im letzten Monat
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?



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2926
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?



  Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: im letzten Monat
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.]



  Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: im letzten Monat
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 :=)



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2926
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.



  Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: im letzten Monat
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






  Profil  Quote  Link auf diesen Beitrag Link
Nastypasty
Junior Letzter Besuch: im letzten Monat
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. :)




  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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]