Informatik - formale Sprachen - DFAs/NFAs

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Informatik - formale Sprachen - DFAs/NFAs

      Moin,
      frage hier mal nach, da ds.de best und hier auch einige Informatik studieren.

      Hab ein paar Fragen zu dem Thema formale Sprachen.
      Und zwar haben wir in einer Aufgabe mehrere Sprachen gegeben und sollen zeigen, ob es einen DFA gibt (oder nicht), der die Sprache L1, L2, usw. entscheidet.
      Nun bezieht sich meine Frage auf die Vorgehensweise bei solchen Aufgaben:
      Sei L := { w | Das vorletzte Zeichen von w ist 7} wobei 7 (natürlich) im Alphabet ist.
      Das diese Sprache von einem DFA entschieden werden kann, ist mir klar.
      -Reicht es als Beweis aus, einen DFA als 5-Tupel oder als Graphen anzugeben?
      -Reicht es, eine reguläre Grammatik G anzugeben, sodass L = L(G) ist? Wir hatten in der Vorlesung gezeigt, dass jede reguläre Sprache von einem DFA entschieden werden kann.
      -Oder stumpf beweisen (z.B. mit dem Pumping-Lemma).

      Dann habe ich hier noch die Sprache L := { w | w ist Dezimaldarstellung einer durch 43 teilbaren Zahl }.
      Wie zeigt man ohne evtl. Teilbarkeitsregeln (ich kenne zumindest keine für 43), dass es einen DFA gibt, der L entscheidet (intuitiv würde ich zumindest behaupten, dass es einen gibt, weil es auch einen für L := { w | w ist Dezimaldarstellung einer durch 3 teilbaren Zahl } gibt).


      DFA = DEA; NFA = NEA für die Deutschen.

      Würde mich über Antworten freuen.

      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • ja, einen automaten angeben der die sprache erkennt reicht.
      grammatik angeben sollte auch reichen (mit verweis auf den satz, und ggf. mit kurzer erklärung warum sie regulär ist).

      ansatz zu durch 43 teilbaren zahlen:
      anhand der äquivalenzrelation X -> (X modulo 43) kannst du alle natürlichen zahlen X in 43 äquivalenzklassen einteilen...
      habt ihr schon den satz von myhill-nerode gehabt?

    • RTC schrieb:

      ja, einen automaten angeben der die sprache erkennt reicht.
      grammatik angeben sollte auch reichen (mit verweis auf den satz).

      Ah gut. Da war ich mir nämlich nicht sicher, ob das reicht.

      RTC schrieb:


      ansatz zu durch 43 teilbaren zahlen:
      anhand der äquivalenzrelation X -> (X modulo 43) kannst du alle natürlichen zahlen X in 43 äquivalenzklassen einteilen...
      habt ihr schon den satz von myhill-nerode gehabt?

      Den Satz hatten wir noch nicht.
      Die Idee mit den Restklassen klingt interessant. Allerdings kann der DFA doch keine Operationen durchführen. Und es gibt unendlich viele Zahlen, die durch 43 teilbar sind. Wie kann der DFA dann ein String akzeptieren?


      edit: ah ok also mit dem Satz von Myhill-Nerode ist die Aufgabe ja einfach^^ Die Menge (X modulo 43) ist endlich -> reguläre Sprache, jedoch hatten wir den Satz noch nicht :(

      Vielen Dank für die schnelle Antwort :thumbup:

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Yarox ()


      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • bump

      zur teilbarkeit durch m:

      x mod m erzeugt genau m restklassen. jede kriegt einen zustand im automaten.
      wenn eine zahl in einer restklasse liegt und dann noch eine ziffer gelesen wird, ändert sich die restklasse auf eine bestimmte weise.
      beispiel zu m=3:

      für m = 43 hättest du 43 zustände.
      das zu konstruieren ist krebs, solltest dir also nen ordentlichen beweis überlegen. dazu bin ich grad zu faul.

    • Okay ich bins wieder.
      Hab eine Frage zum Aufschrieb, ob der folgende Beweis so okay ist. Geht ums Pumping-Lemma. Also mir gehts echt nur um den optimalen Aufschrieb!

      zZ.: Es existiert kein DFA, der die Sprache L := { w in {0,1}* | |w| ist Primzahl} entscheidet.
      Beweis: Angenommen es existiert ein DFA M:=(Q,{0,1},d,q,F), der L entscheidet. Dann gibt es für alle n eine Zerlegung der Form z=uvw derart, dass
      |uv| <= n und |v| >=1 gilt so, dass uv^iw in L liegt.
      2 ist die kleinste Primzahl. Betrachte also Q = { q, q' }. Dann ist |Q| = n = 2.

      Sei z = uvw mit u =1 v={0,1}, w das leere Wort. Dann ist |uv|<=n und |v| >=1, also gilt bzgl. der Zerlegung das Pumping Lemma.
      Weiter folgt v=1, ansonsten wäre L(M) != L, weil 11 Element von L ist, 10 aber nicht.
      Sei nun i=2 >=0, das heißt, z = 111. 111 = 3*37 ist nicht Element von L.
      Somit haben wir ein i gefunden, sodass z=uv^iw nicht in L(M).
      Also ist L(M) != L. Widerspruch zur Annahme, dass M L entscheidet.

      Ist das so formal richtig?
      I'm still not sure ~.~

      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • Yarox schrieb:

      Okay ich bins wieder.
      Hab eine Frage zum Aufschrieb, ob der folgende Beweis so okay ist. Geht ums Pumping-Lemma. Also mir gehts echt nur um den optimalen Aufschrieb!

      zZ.: Es existiert kein DFA, der die Sprache L := { w in {0,1}* | |w| ist Primzahl} entscheidet.
      Beweis: Angenommen es existiert ein DFA M:=(Q,{0,1},d,q,F), der L entscheidet. Dann gibt es für alle n eine Zerlegung der Form z=uvw derart, dass
      |uv| <= n und |v| >=1 gilt so, dass uv^iw in L liegt.
      2 ist die kleinste Primzahl. Betrachte also Q = { q, q' }. Dann ist |Q| = n = 2.

      Sei z = uvw mit u =1 v={0,1}, w das leere Wort. Dann ist |uv|<=n und |v| >=1, also gilt bzgl. der Zerlegung das Pumping Lemma.
      Weiter folgt v=1, ansonsten wäre L(M) != L, weil 11 Element von L ist, 10 aber nicht.
      Sei nun i=2 >=0, das heißt, z = 111. 111 = 3*37 ist nicht Element von L.
      Somit haben wir ein i gefunden, sodass z=uv^iw nicht in L(M).
      Also ist L(M) != L. Widerspruch zur Annahme, dass M L entscheidet.

      Ist das so formal richtig?
      I'm still not sure ~.~

      Ich weiß, dir gehts nur um das Aufschreiben, aber dein Beweis ist falsch:
      Wenn ich mich richtig erinnere, besagt das Pumping-Lemma nicht, dass dies für alle natürlichen Zahlen gilt, sondern lediglich, dass eine natürliche Zahl n exestiert, sodass die Aussage des Lemmas gilt, d.h. du kannst dir dein n nicht festlegen.
      Sei also n die Konstante des Pumping-Lemmas, d.h.
      alle Wörter z aus L mit |z| >= n lassen sich zerlegen, wie du bereits geschrieben hast.
      Betrachte dann einfach mal das Wort 0^p mit p>=n Primzahl. (gibt unendlich viele Primzahlen, also exestiert solch ein p)
      => 0^p = 0^(|uvw|) . Und jetzt schau ob du daraus mit den Aussagen des Pumping Lemmas nen Widerspruch hinkriegst.

      LG

    • Oh man wollte das gar nicht mehr abschicken ~.~ Man beachte die Uhrzeit^^

      vergiss was hier stand, ich editiere sobald ich was habe...

      edit:
      Betrachte also 0^p = 0^(|uvw|) mit |uv|<=n;|v|>=1.
      Es gilt:
      0^(|uvw|) = 0^(|u|+|v|+|w|) = 0^(|u|) 0^(|v|) 0^(|w|).
      Nach dem Pumping Lemma gilt für alle i>=1, 0^(|u|) 0^(|v|)^(i) 0^(|w|). ist in L(M).
      Sei nun i=2, dann gilt für |v|=1:
      0^(|u|) 0^(|v|)^(2) 0^(|w|)=
      0^(|u|) 0^(|v|+1) 0^(|w|)=
      0^(|u|+|v+1|+|w|)=
      0^(|uvw|)0
      Da uvw eine Primzahl war ist |0^(|uvw|)0| gerade, also keine Primzahl.
      Somit ist |0^(|uvw|)0| nicht in L(M).
      Widerspruch zur Annahme, L(M)=L

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von Yarox ()


      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • Yarox schrieb:

      Oh man wollte das gar nicht mehr abschicken ~.~ Man beachte die Uhrzeit^^

      vergiss was hier stand, ich editiere sobald ich was habe...

      edit:
      Betrachte also 0^p = 0^(|uvw|) mit |uv|<=n;|v|>=2.
      Es gilt:
      0^(|uvw|) = 0^(|u|+|v|+|w|) = 0^(|u|) 0^(|v|) 0^(|w|).
      Nach dem Pumping Lemma gilt für alle i>=1, 0^(|u|) 0^(|v|)^(i) 0^(|w|). ist in L(M).
      Sei nun i=2, dann gilt:
      0^(|u|) 0^(|v|)^(2) 0^(|w|)=
      0^(|u|) 0^(|v|+1) 0^(|w|)=
      0^(|u|+|v+1|+|w|)=
      0^(|uvw|)0
      Da uvw eine Primzahl war ist |0^(|uvw|)0| gerade, also keine Primzahl.
      Somit ist |0^(|uvw|)0| nicht in L(M).
      Widerspruch zur Annahme, L(M)=L

      0^(|v|)^2 = 0^|v|0^|v|=0^(2*|v|) =/= 0^(|v|+1)
      D.h. für dein gewähltes i=2,
      müsstest du zeigen, dass |u|+2*|v|+|w| keine Primzahl sein kann.
      Gilt aber nicht, denn z.B. |u| = 1, |v|=2, |w|=0, dann ist |uvw|=3, und |u|+2*|v|+|w|=5 ist auch eine Primzahl.
      Probiere mal lieber i=p+1 zu setzen, mit ein wenig umstellen kriegt man dann nen Widerspruch zur Primzahl-eigenschaft von |uv^iw| .

      LG

    • Ayo ich seh schon woraufs hinausläuft^^. (hatte editiert, dass |v|=1 ist, aber okay der ansatz war nicht so schön)
      mit i=p+1 haben wir später dann 0^z 0^p aber z und p waren primzahlen => p+z ist gerade => p+z keine primzahl.

      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • Yarox schrieb:

      Ayo ich seh schon woraufs hinausläuft^^. (hatte editiert, dass |v|=1 ist, aber okay der ansatz war nicht so schön)
      mit i=p+1 haben wir später dann 0^z 0^p aber z und p waren primzahlen => p+z ist gerade => p+z keine primzahl.

      Achso hatte ich überlesen mit |v|=1, aber das darfst du auch nicht festlegen. Ähm kann nicht genau nachvollziehen wie du auf p+z kommst(z ist auch keine Zahl, sondern das Wort der Länge p), ich schreib einfach mal die Lösung auf, wie ich mir das gedacht hatte:
      Für i=p+1 gilt:
      |uv^iw| = |uv|+i*|v| = |uv|+(p+1)|v| = |uv|+|v|+p*|v|= |uvw| + p*|v| = p + p*|v| = p*(|v|+1)
      => p und (|v|+1) sind 2 nicht-triviale Teiler von |uv^iw|
      => |uv^iw| ist keine Primzahl
      => 0^|uv^iw| ist nicht aus L
      => L ist nicht regulär.

      LG

    • |uv^iw| = |uv|+i*|v|
      verstehe ich jetzt nicht.
      Wie verschwindet da das w?
      uv^iw = uv^{p+1}w = uvw+v^p = p+v^p
      (in Beträgen) hätte ich jetzt eher.

      edit: okay hab die letzte gleicheit auch auf meinem blatt, die schlussfolgerung fehlte mir nur ~.~

      Heinrich von Kleist schrieb:

      [...] [D]u hast an mir getan, [...] was in Kräften [...] eines Menschen stand, um mich zu retten: Die Wahrheit ist, daß mich auf Erden nicht zu helfen war.

    • Yarox schrieb:

      |uv^iw| = |uv|+i*|v|
      verstehe ich jetzt nicht.
      Wie verschwindet da das w?
      uv^iw = uv^{p+1}w = uvw+v^p = p+v^p
      (in Beträgen) hätte ich jetzt eher.

      Sorry ich meine |uw|, verschrieben. Und ja, dann hast du ja genau das gleiche was ich geschrieben habe, p+|v^p| = p+p*|v|, etc.

      LG

    • Benutzer online 1

      1 Besucher