Die Mathe-Redaktion - 21.08.2018 04:31 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
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 277 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Algorithmus NEA\e ohne e-Übergänge
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Algorithmus NEA\e ohne e-Übergänge
werdas34
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2018
Mitteilungen: 28
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-07-22


Hallo,

ich habe folgendes Video gesehen, womit man relativ einfach den NEA ohne e-Übergänge konstruieren kann:
www.youtube.com/watch?v=Ssx_Xg0irOI

Meine Frage jetzt:
Funktioniert das mit jedem NEA\e richtig sprich äquivalent zu dem NEA?

Ich finde nichts derartiges im Netz. Und weitere Beispiele die dies so machen, wie im Video finde ich leider auch nicht.

Ich habe es natürlich auch bei einem anderen NEA\e ausprobiert, wo ich eine Lösung besitze, aber da kommt was anderes raus, was aber durch das "Äquivalenzkonzept" nichts bedeuten muss.

Wäre froh wenn mir jemand sagen kann, ob dies immer gilt?
Also bestätigen, das dies ein richtiger Algorithmus ist um einen NEA\e in einen NEA ohne e-Übergange zu überführen.

Vielen Dank.
mfg werdas34



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1276
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-07-23

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Der Algorithmus, der da vorgeführt wird, funktioniert nicht. Z.B. müsste man von q1 beim Lesen von 0 ja auch in q3 landen können.

Besser wären die Einträge in der neuen Übergangstabelle
$$\displaystyle\delta'(s,c) = \bigcup_{(s' \in \delta(s,\varepsilon^*))} \bigcup_{(s'' \in \delta(s',c))} \delta(s'',\varepsilon^*),$$
also: erst beliebig viele epsilon-Schritte, dann ein echter Schritt, dann wieder beliebig viele epsilon-Schritte.
Im Video wird nur
$$\displaystyle\delta'(s,c) = \bigcup_{(s' \in \delta(s,\varepsilon^*))} \delta(s',c)$$
gesetzt.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
werdas34
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2018
Mitteilungen: 28
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-07-23


Danke für deine Antwort.

Ich habe mit meinem Professor darüber gesprochen und er meinte es sei im Grunde der selbe Algorithmus den wir hatten, nur eben anders hingeschrieben.

Wir suchen auch die transitive e-Hülle. Und das selbe wird im Video auch gemacht. Da halt der neue NEA nicht eindeutig ist, ist es für mich grade recht schwierig zu sagen, ob dies wirklich stimmt.

Denn das was du bemängelst hätte ich auch gesehen, von dem her.

Ich werde aber diesen Algorithmus morgen in meiner Prüfung verwenden, falls NEA/e zu NEA drankommt. Da der Professor ja gesagt hat, sie seien in der Vorgehensweise gleich (zu unserem).

Dazu finde ich den Algortithmus viel einfacher und schneller hingepinselt für eine Prüfung als den anderen.

Dennoch Danke.

Mit freundlichem Gruß,
werdas34



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1276
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-07-23


Man kann die sich an "richtige" Schritte anschließenden epsilon-Schritte auch weglassen, aber dann muss man die Endzustandsmenge ändern: Alle Zustände, von denen aus man einen Endzustand durch epsilon-Schritte erreichen kann, müssen selbst Endzustände werden.

Beispiel: Betrachte diesen Automat (an dem sehe ich gerade, dass meine Ergänzung nachfolgender Epsilonschritte ja auch nicht immer reicht):
     eps
  1 -----> 2
wobei 1 der Startzustand ist und 2 der einzige Endzustand. Offenbar akzeptiert er das leere Wort und sonst nichts. Das Ergebnis der Übersetzung im Video akzeptiert kein einziges Wort, wenn man die Endzustandsmenge lässt, wie sie ist.



  Profil  Quote  Link auf diesen Beitrag Link
werdas34
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2018
Mitteilungen: 28
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-07-23


Wenn ich dich richtig verstehe, bereitet dir die Endzustände im Video Probleme, da sie so bleiben wie sie ursprunglich waren.

Jedoch hat der Video-Ersteller in der Beschreibung erwähnt, dass q2 auch zu einem Endzustand wird. Da fed-Code einblenden

fed-Code einblenden

In deinem Beispiel sehe ich es genauso:
  fed-Code einblenden
Also auch 1 Endzustand und zugleich Startzustand ist auch das leere Wort möglich bzw. die einzige Lösung.
fed-Code einblenden




  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1276
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-07-23


Ah, okay, die Beschreibung hatte ich nicht gelesen. Dann ist ja jetzt alles klar.  smile



  Profil  Quote  Link auf diesen Beitrag Link
werdas34 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    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-2018 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]