Die Mathe-Redaktion - 28.02.2020 21:50 - 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 429 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
 
Suchwörter   (werden UND-verknüpft)
Keines der folgenden   keine eigenen Beiträge
Name des Autors 
resp. Themenstellers 

nur dessen Startbeiträge
auch in Antworten dazu
Forum 
 Suchrichtung  Auf  Ab Suchmethode  Sendezeit Empfehlungbeta [?]
       Die Suche erfolgt nach den angegebenen Worten oder Wortteilen.   [Suchtipps]

Link auf dieses Suchergebnis hier

Forum
Thema Eingetragen
Autor

Komplexitätstheorie
Universität/Hochschule 
Thema eröffnet von: Landjalan
Zusammengesetztheits-Problem ist in NP  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-01-23
Bilbo
 

2020-01-23 09:56 - stpolster in Beitrag No. 1 schreibt:
Ich dachte, dass der Prinzahltest mittlerweile nicht mehr zu NP gehört.
siehe de.wikipedia.org/wiki/AKS-Primzahltest

Oder habe ich wieder etwas falsch verstanden.

LG Steffen

Hallo Steffen,

es geht hier ja nicht darum zu zeigen, dass das Problem NP-schwer ist. Da <math> \bf{P} \subseteq \bf{NP}</math> gilt, widerspricht die schärfere Aussage "PRIMES is in P" nicht dem, was Landjalan zeigen möchte (und der Primzahltest gehört immer noch zu NP).

@Landjalan: Die ganz grobe Idee sollte sein, dass Du nichtdeterministisch eine Zahl rätst und dann prüfst, ob diese ein Teiler deiner Eingabe ist. Wie man das technisch-formal genau macht, muss natürlich noch etwas ausformuliert werden.

Viele Grüße

Thorsten

Bug- und Request-Tracker
  
Thema eröffnet von: viertel
Seltsames Thread-Display  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-01-17
Bilbo
J

2020-01-17 02:52 - viertel im Themenstart schreibt:
Leider nicht reproduzierbar ☹️

Bei mir schon. Es sieht bei mir genauso aus, außer dass links oben nur Seite 53 statt 54 steht.

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: pram
Sprache nicht regulär: Direkte Argumentation über Automaten  
Beitrag No.5 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-17
Bilbo
J

Hallo pram,

wäre das Wort <math>b^jab^{2i+1}</math> in der Sprache, dann müsste es ein Wort <math>w \in \{a,b\}^+</math> geben, für das gilt: <math>b^jab^{2i+1} = waw^Rbw</math>.

Das Wort auf der linken Seite dieser Gleichung enthält aber nur ein <math>a</math> - somit ist klar, dass das <math>a</math> links mit dem <math>a</math> nach dem Wort <math>w</math> auf der rechten Seite übereinstimmt. Und damit folgt, dass <math>w=b^j</math> sein muss (da der Teil links von dem <math>a</math> auf der einen Seite dem Teil links von dem <math>a</math> auf der anderen Seite entsprechen muss).

Dann hat aber das Wort auf der rechten Seite insgesamt die Länge <math>\abs{w}+1+\abs{w^R}+1+\abs{w} = j +1 +j +1 +j = j + 2 + 2j</math>, während das Wort auf der linken Seite offensichtlich die Länge <math>j + 2 + 2i</math> besitzt. Das kann nur sein, wenn <math>i=j</math> ist, im Widerspruch zur Wahl von <math>i</math> und <math>j</math>.

Ist es damit klar?

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: pram
Sprache nicht regulär: Direkte Argumentation über Automaten  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-17
Bilbo
J

Hallo pram,

ach so meinst du das, danke für die Erklärung.

Da müsste man hier doch ganz analog argumentieren können, indem man sich die Wörter <math>b^1, b^1, ..., b^{\abs{Q} + 1}</math> anschaut und wieder so ein Paar <math>i \neq j</math> sucht. Dann gilt <math>b^i a b^{2i+1} \in L_1</math>, aber <math>b^j a b^{2i + 1} \notin L_1</math>.

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: pram
Sprache nicht regulär: Direkte Argumentation über Automaten  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-17
Bilbo
J

Hallo pram,

was meinst Du mit "direkte Argumentation über Automaten"? Durch Angabe eines Automaten zeigst Du, dass eine Sprache regulär ist; dass sie nicht regulär ist, zeigt man meist am einfachsten mit dem Pumping-Lemma - in diesem Fall bietet sich beispielsweise das Wort an, das für <math>w=b^p</math> entsteht, wobei <math>p</math> die Konstante für <math>L_1</math> wie im Pumping-Lemma ist.

Oder schwebt Dir eine Art der Argumentation vor?

Viele Grüße
Thorsten

Gruppen
Universität/Hochschule 
Thema eröffnet von: Math_user
Die Ordnung von f(x) teilt die Ordnung von x  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-02
Bilbo
J

Hallo Math_user,

schreibe <math>d = m\cdot \delta + n</math> mit <math>m \in \mathbb{N}</math> und <math>0 \leq n < \delta</math>. Angenommen, es gälte <math>n > 0</math>, dann hätte man:

 <math>\displaystyle e = f(x) ^d = f(x)^{m\cdot \delta + n} = ((f(x))^\delta)^m \cdot (f(x))^n = e^m \cdot (f(x))^n = (f(x))^n</math>,

was aber wegen <math>0 < n < \delta</math> der Definition der Ordnung widerspricht.

Viele Grüße

Thorsten

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: pram
Obere Schranken für die Kolmogorov-Komplexität  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-02
Bilbo
J

Hallo pram,

ja, genau, oder eben

<math>K(w_n) \leq 3 log_2(n) + c_C</math>.

Neben dem Logarithmusgesetz habe ich da auch noch das Aufrunden sowie das "+1" weggelassen, da diese ja durch eine entsprechende Erhöhung der Konstante <math>c_C</math> abgefangen werden können.

Viele Grüße
Thorsten

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: pram
Obere Schranken für die Kolmogorov-Komplexität  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-10-02
Bilbo
J

Hallo pram,

meinst Du wirklich <math>(log_2(n + 1))^2</math>, oder nicht doch eher <math>log_2(n^2 + 1)</math>? Letzteres könntest Du noch geringfügig vergröbern zu <math>log_2((n+1)^2))</math> und die Ungleichung dann noch weiter vereinfachen.

Viele Grüße
Thorsten

Programmieren
Universität/Hochschule 
Thema eröffnet von: lissy1234567
mglearn in Python  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-09-23
Bilbo
J

Hallo lissy,

wie gesagt, lizenzrechtlich wirst Du deswegen sicherlich keine Probleme bekommen, warum auch. Eine andere Frage ist, ob der Betreuer deines Seminars solche externen Nichtstandard-Bibliotheken zulässt. Das könntest du mit ihm selbst klären. Da du vermutlich aber ja nur einzelne Teile benötigst, würde ich die entsprechenden py-Dateien aus dem GitHub herunterladen und deiner Abgabe beifügen, so dass das Ganze ohne weitere Vorarbeiten lauffähig ist. Natürlich solltest Du dann - entsprechend einem Zitat - erwähnen, dass diese Codefragmente nicht von Dir stammen.

Viele Grüße

Thorsten

Programmieren
Universität/Hochschule 
Thema eröffnet von: lissy1234567
mglearn in Python  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-09-23
Bilbo
J

Hallo lissy,

unter https://www.oreilly.com/library/view/introduction-to-machine/9781449369880/ch01.html finde ich Folgendes:

The accompanying code includes not only all the examples shown in this book, but also the mglearn library. This is a library of utility functions we wrote for this book, so that we don’t clutter up our code listings with details of plotting and data loading.


Dies bestätigt also deine Vermutung, dass diese Bibliothek extra für das Buch konzipiert wurde, um auf Hilfsfunktionen etc. zugreifen zu können, die nicht direkt etwas mit dem Buchthema zu tun haben. Da die Bibliothek sich im GitHub befindet (einem Filehoster für Quellcodedateien etc. - siehe hier), kann man allerdings problemlos darauf zugreifen, auch ohne das Buch zu besitzen. Ich nehme mal an, dass Du den Code nicht ohne Weiteres für kommerzielle Software verwenden darfst - jedenfalls sehe ich dort keine entsprechende Lizenz. Im Privatbereich sollte das aber kein Problem sein.

Viele Grüße

Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: smirk_mirkin
DFA-Minimierung: Kürzeste Zeugen sind durch Anzahl der Zustände begrenzt  
Beitrag No.5 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-25
Bilbo
 

Hallo smirkin_mirkin,

stimmt, so sollte das gehen.

Ich bin zwischenzeitlich im Wesentlichen zu demselben Ergebnis gekommen, wobei ich die Äquivalenzrelation etwas anders (nämlich nicht induktiv) definiert habe:

<math>q_1 \equiv_k q_2 \iff (\forall w) (|w| \leq k \rightarrow (q_1w \in F \leftrightarrow q_2w \in F))</math>

So aufgeschrieben, ist es dann trivial, dass die Nicht-k-Äquivalenz dasselbe bedeutet wie die Existenz kurzer Zeugen; dafür muss man für die Verfeinerungseigenschaft noch etwas zeigen, die bei deiner Definition wiederum trivial ist. Letztlich also der gleiche Beweis wie bei dir.  😄  

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: smirk_mirkin
DFA-Minimierung: Kürzeste Zeugen sind durch Anzahl der Zustände begrenzt  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-25
Bilbo
 

Hallo smirk_mirkin,

das hört sich vernünftig an und ist wohl auch das, was unter http://www.in.tu-clausthal.de/uploads/media/MSc-Complexity-Theory-official-slides.pdf gemacht wird (Theorem 1.25 / Lemma 1.26, leider ohne Definition der Äquivalenzrelation und ohne Beweis).

Wieso gilt die Aussage mit den Verfeinerungen?
Der Automat mit der Zustandsmenge <math>\{z_0, z_1\}</math>, Startzustand <math>z_0</math>, Endzustand <math>z_1</math> und den Übergängen
<math>z_0 \overset{0,1}{\longrightarrow} z_1</math>
<math>z_1 \overset{0,1}{\longrightarrow} z_1</math>
scheint mir doch ein Beispiel zu sein, bei dem <math>z_0 \not\equiv_0 z_1</math> gilt, aber <math>z_0 \equiv_1 z_1</math> (da für alle <math>a \in \{0,1\}</math> gilt, dass <math>z_0a = z_1a = z_1</math>). Wahrscheinlich unterläuft mir dabei irgendein blöder Denkfehler.

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: smirk_mirkin
DFA-Minimierung: Kürzeste Zeugen sind durch Anzahl der Zustände begrenzt  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-25
Bilbo
 

Hallo smirk-mirkin,

ich kann Deine Frage leider auch nicht beantworten. Ich finde sie allerdings sehr interessant und möchte sie gern nochmal nach vorne holen.

Da die Länge des kürzesten Zeugen ja a priori nur quadratisch in der Anzahl der Zustände beschränkt ist, habe ich längere Zeit versucht, ein Gegenbeispiel zu Deiner Vermutung zu konstruieren, allerdings auch ohne Erfolg.

Wenn Du die Antwort findest, teil sie doch bitte mal mit.  😄 Oder vielleicht hat jemand anderes eine Idee.

Viele Grüße
Thorsten

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: egf
Definition Trivialität von Indexmengen (wie im Satz von Rice)  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-20
Bilbo
J

Hallo egf,

für jede Turingmaschine <math>M</math> ist <math>L(M) = \{w: M(w)</math> hält in einem akzeptierenden Zustand <math>\}</math> rekursiv aufzählbar. Also ist die Menge <math>\{\langle M \rangle: L(M) \in RE\}</math> die Menge aller Turingmaschinencodes.

Und nochmal: Auch eine Maschine, die niemals anhält - weder in akzeptierenden noch in verwerfenden Zuständen - akzeptiert trotzdem eine Sprache, nämlich die leere Sprache. (Klar, man kann die leere Sprache auch durch eine totale Maschine akzeptieren lassen, aber darum geht es Dir ja nicht.)

Viele Grüße
Thorsten

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: egf
Definition Trivialität von Indexmengen (wie im Satz von Rice)  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-19
Bilbo
J

Hallo egf,

ich sehe keinen wesentlichen Unterschied zwischen der Definition auf Wikipedia und der von mir verwendeten. Außer dass bei Wikipedia von der Menge der Funktionen selbst gesprochen wird, während ich von deren Kodierungen gesprochen habe.

Die Wikipedia-Definition zieht "alle partiellen Turing-berechenbaren Funktionen" in Betracht. Darunter ist auch die nirgendwo definierte Funktion; und diese wird gerade von einer bei keiner Eingabe haltenden Turingmaschine partiell berechnet.

Und zu dem Beispiel, das du bringst, schreibst Du

es gibt natürlich auch Kodierungen von TMs, die keine Sprache akzeptieren

Ich weiß nicht, wie Du das meinst, aber in dem zu betrachtenden Kontext (Turingmaschinen mit akzpetierenden und nicht akzeptierenden Endzuständen) stimmt diese Aussage nicht. Jede Turingmaschine akzeptiert ihren eigenen Definitionsbereich, also die Menge der Eingaben, bei denen die Maschine in einem akzeptierenden Zustand hält. Auch hier gilt wieder, dass diese Menge leer sein kann (zum Beispiel, falls die Maschine nirgendwo hält).

Viele Grüße
Thorsten

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: felix_macht_mathe
Sind folgende Sprachen entscheidbar? (u.a. Satz von Rice)  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-19
Bilbo
 

Hallo zusammen!

@egf:
2019-07-18 15:04 - egf in Beitrag No. 2 schreibt:
Es ginge mir um die Klammer: "eine, die nie hält": Das wäre mMn nicht zulässig, denn eine Solche erkennt ja gar keine Sprache, resp. dann wäre ja jede Sprache nicht-trivial.

Nein, das stimmt so nicht. Trivialität ist ja eine Eigenschaft einer Indexmenge, also einer Menge von Maschinenkodierungen. Und Nichttrivialität bedeutet in diesem Zusammenhang nur, dass es mindestens eine Maschine gibt, deren Kodierung in dieser Menge enthalten ist und mindestens eine, deren Kodierung nicht darin enthalten ist. Dabei sind alle Maschinen zu berücksichtigen, egal ob sie überall halten oder nur manchmal oder nirgendwo.


{L(M) hat zwei Wörter der selben Länge} wäre für mich semi-entscheidbar, da ich theoretisch eine TM darauf ansetzen könnte, die als Input das erste Wort von L(M) empfängt, die Länge mit allen anderen Wörtern in L(M) abgleicht, und entweder 1 bei gleicher Länge ausgibt, oder so lange weiter sucht, bis alle Wörter ausprobiert wurden... aber was, wenn die Sprache unendlich viele Wörter besitzt  confused Dürfte ich auch sagen, dass ich zuerst einen Algorithmus laufen lasse, der meine Sprache L(M) nach der Wörterlänge sortiert und dann immer eine Wortlänge |wi| mit |w(i+1)| vergleiche?

Erst einen solchen Sortieralgorithmus laufen zu lassen, funktioniert leider auch nicht, da Du ja bei einer unendlichen Sprache immer noch das Problem hättest, dass dieser unendlich lange laufen würde. Einen Ausweg bietet die sogenannte Dovetailing-Methode: Dabei versuchst Du, für alle Eingabepaare <math>(w, w") \in \Sigma^\ast \times \Sigma^\ast</math> parallel zu vergleichen, ob <math>M(w)</math> und <math>M(w")</math> die gleiche Länge haben. Was damit gemeint ist, habe ich hier schon mal erklärt: dove-tailing

Sprache 1 müsste eigentlich semi-entscheidbar sein, da es ja im Grunde das rekursiv-aufzählbare Wortproblem beschreibt (mit der Frage: sind 0 & 1 Teil der Sprache)

Achtung, die Frage ist nicht: "Sind 0 und 1 Teil der Sprache?" Sondern hier: "Sind 0 und 1 die einzigen Wörter der Sprache?"
Das ist eine deutliche Verschärfung ...

Sprache 2 kann eigentlich nicht entscheidbar sein, da dadurch dass sie co-semi-entscheidbar ist, würde sie ja durch Semi-Entscheidbarkeit wiederum insgesamt entscheidbar werden.

Jetzt drehst Du dich im Kreis. Du sagst: Sie kann nicht entscheidbar sein, denn sonst wäre sie ja entscheidbar. 😄 Nein, da muss noch eine andere Begründung her (vergleiche auch die anderen beiden Sprachen).

Sprache 3 könnte semi-entscheidbar sein, wenn ich eine TM auf das Problem ansetze, soll sie 1 ausgeben, wenn die erste binärkodierte Quadratzahl erkannt wurde und die nächste überprüfen, ansonsten weitersuchen. Hier bin ich mir aber ziemlich unsicher...

Na, das passt von der Begründung her noch nicht so ganz, auch wenn ich mit der Semi-Entscheidbarkeit einverstanden bin. Versuch mal, es genau zu formulieren: Du willst eine Maschine <math>M"</math> konstruieren, die bei Eingabe <math>w \in \Sigma^\ast</math> die Ausgabe 1 liefert (und hält), wenn <math>w</math> in <math>L</math> liegt, und sonst nicht anhält. Bei Eingabewort <math>w</math> prüft <math>M"</math> nun zuerst, ob <math>w</math> die Kodierung einer Turingmaschine <math>M</math> ist, also ob <math>w = \langle M \rangle</math> für ein <math>M</math> gilt. Falls ja, dann ...
Kriegst du den Rest selbst hin?

Viel Erfolg und viele Grüße
Thorsten




Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: felix_macht_mathe
Sind folgende Sprachen entscheidbar? (u.a. Satz von Rice)  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-18
Bilbo
 

Hallo Felix,

Deine Aussagen, dass die erste und die dritte Sprache nach dem Satz von Rice nicht entscheidbar seien und die zweite co-semi-entscheidbar ist, stimmen schon mal.  😄

Noch zwei Kommentare von mir zu Deinen Begründungen:

Es gibt ja sowohl eine TM, die eben nur L(M) = {0,1} beschreibt, aber auch eine TM, die Sigma∗ \ {0,1} beschreibt?

Das ist zwar als Begründung für die Nichttrivialität der Menge korrekt, allerdings würde für den zweiten Teil auch reichen, irgendeine Maschine zu nehmen, die nicht <math>\{0,1\}</math> erkennt (zum Beispiel eine, die nie hält). Die Sprache <math>\Sigma^\ast \setminus \{0,1\}</math> spielt hier keine Sonderrolle. Wie gesagt, ich erwähne das nur, um Missverständnisse bei Dir auszuschließen.

Wäre für mich co-semi-entscheidbar, da es ja semi-entscheidbar ist ob eine Sprache nur Wörter der selben Länge hat.

Das stimmt als Begründung so nicht. Die Sprache
<math>\{\langle M\rangle: L(M) </math> hat nur Wörter derselben Länge<math>\}</math>
ist nicht semi-entscheidbar. Denn dafür müsste man eine Maschine <math>M</math> auf allen Eingaben laufen lassen, was in endlicher Zeit nicht möglich ist. Die Sprache ist aber co-semi-entscheidbar.

Allerdings geht es gar nicht um diese Sprache, sondern du musst die Sprache
<math>\{\langle M\rangle: L(M) </math> hat zwei Wörter derselben Länge<math>\} \cup\{w: w</math> ist keine Kodierung einer Turingmaschine <math>\}</math>
betrachten. Der zweite Teil ist entscheidbar, du musst also noch begründen, warum der erste Teil semi-entscheidbar ist.

Außerdem hast du noch keine Aussage darüber getroffen
- ob die erste Sprache zumindest semi- oder co-semi-entscheidbar ist.
- ob die dritte Sprache zumindest semi- oder co-semi-entscheidbar ist.
- ob die zweite Sprache vielleicht sogar entscheidbar ist.

Was fällt dir denn zu diesen Fragen ein?

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Schule 
Thema eröffnet von: Ehemaliges_Mitglied
Dreiband-TM: Fehler in Musterlösung?  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-17
Bilbo
 

Hallo Zrebna,

du hast recht, dieser Übergang fehlt. Es fehlen aber auch noch weitere Übergänge für den Fall, dass <math>x_1</math> länger als <math>x_2</math> ist oder umgekehrt. Alternativ könnte man per Konvention vereinbaren, dass man in diesen Fällen zusätzliche Nullen vor die Zahlen schreibt, um sie gleichlang zu machen, und dass man in jedem Fall eine führende Null davorschreibt, um den von dir erwähnten Fall der Extra-Stelle abzufangen.

Steht in eurem Turingmaschinen-Modell der Lesekopf eigentlich zu Anfang RECHTS der Eingabe? Üblicher ist nämlich eigentlich, dass er links davon steht, dann müsste man auch zuerst ans Ende der Eingabe laufen.

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: NinPanda
Minimalautomaten zu NFA  
Beitrag No.5 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-17
Bilbo
 

Hallo Zrebna!

2019-07-16 18:58 - Zrebna in Beitrag No. 4 schreibt:
Ah, hab es missverstanden.

Geht ja um die Umwandlung eines Minimalautomaten (deterministisch) in einen NFA und nicht umgekehrt.

Nein, darum geht es nicht. Diese Richtung wäre ja auch trivial, da jeder deterministische Minimalautomat insbesondere ein NFA ist, es da also nichts "umzuwandeln" gibt.

Ich meinte nur, dass NinPanda zwar von einem NFA schreibt, aber in den Voraussetzungen tatsächlich einen DFA gegeben hat.

Viele Grüße
Thorsten

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: NinPanda
Minimalautomaten zu NFA  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2019-07-15
Bilbo
 

Hallo Zrebna,

ich weiß nicht, ob es ein direktes Verfahren gibt, um aus einem NEA einen Minimalautomaten zu konstruieren. Das ist hier aber auch unerheblich, denn anhand der Darstellung der Übergänge in Tabellenform, die NinPanda angibt, sieht man ja, dass es sich bereits um einen deterministischen Automaten handelt.

Viele Grüße
Thorsten
 

Sie haben sehr viele Suchergebnisse
Bitte verfeinern Sie die Suchkriterien

[Die ersten 20 Suchergebnisse wurden ausgegeben]
Link auf dieses Suchergebnis hier
(noch mehr als 20 weitere Suchergebnisse)

-> [Suche im Forum fortsetzen]
 
 

 
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]

used time 0.0651