Die Mathe-Redaktion - 15.10.2018 19:29 - 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
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 523 Gäste und 20 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 » Deterministischen endlichen Automat konstruieren
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Deterministischen endlichen Automat konstruieren
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-04-19


Hallo,
wir sollen einen deterministischen endlichen Automat (DEA) kontruieren, der nur eingaben akzeptiert bei dem die Anzahl der Einsen minus der Anzahl der nullen, 3 mod 4 ergibt.

Zunächst weiß ich nicht ganz genau was das bedeutet. 3 mod 4 ist ja offensichtlich 3, d.h. wenn zum beispiel 7 Einsen und 4 Nullen eingelesen werden, akzeptiert der automat die eingabe, weil 7 - 4 = 3, oder? Das gleiche dann bei 4 Einsen und 1 Null, usw.

Hat da wer eine idee wie so ein Automat aussehen kann? Wir hatten davor noch zwei einfachere aufgaben, da bin ich noch durch glück und googeln drauf gekommen, aber jetzt bin ich überfordert. Weiß auch nicht wie man systematisch an die sache ran geht, falls das überhaupt geht.

mfg



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2340
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-04-19

\(\begingroup\)
Hallo,

gemeint ist, dass $\#1 - \#0 \equiv 3\pmod 4$.



-----------------
⊗ ⊗ ⊗
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-04-19


Hmm ok, ich hab mal etwas gegoogelt und anscheinend bedeutet dann

#1 - #0 = 3 (mod 4) das gleiche wie
(#1 - #0) mod 4 = 3

Das bedeutet es können z.b. auch 3 Einsen und keine 0 eingelesen werden und 3 mod 4 würde dann auch 3 ergeben.

Aber wie ich jetzt den automat mach, da blick ich immer noch nicht durch. Ich würd sagen man braucht zumindest schonmal mindestens 4 Zustände, weil die minimallänge wäre ja 111 (dreimal die Eins), d.h. der 4. Zustand wäre endzustand..



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2340
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-04-19

\(\begingroup\)
Ja, wenn dir der mod-Operator (wohl von der Programmierung her) bekannt ist, kannst du es auch so verstehen. Die erste Schreibweise passt eher zu der Äquivalenzrelation $x\equiv y\pmod m$ stehend für "x und y haben bei der Division durch m den gleichen Rest".

Deine Überlegung ist zunächst richtig, du brauchst mindestens 4 Zustände. Es geht auch naheliegend mit genau 4 Zuständen (korrespondierend zu den 4 möglichen Divisionsresten 0, 1, 2, 3).
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-04-19


So also ich hab es mal so probiert:



stimmt das? q3 ist endzustand.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2340
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-04-19


Das Bild ist ziemlich klein, ich kann es kaum erkennen, aber es sieht so aus würde von q3 kein Pfeil mit einer 1 herausführen.


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



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-04-19


Ok im Bild sieht man gar nichts. Folgende tabelle:

    0  1
q0  q1 q1
q1  q0 q2
q2  q1 q3
q3  q2 q2

Das heißt von q3 geht bei Eingabe von 1 oder 0 jeweils in den zustand q2.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2340
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-04-19


Warum nach q2? Das würde ja dann heißen dass man nach 5 1en in q3 landet.



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-04-19


Ja stimmt. Dann wohl von q3 bei Eingabe von 1 nach q0. D.h. so:

    0  1
q0  q1 q1
q1  q0 q2
q2  q1 q3
q3  q2 q0

Aber kann auch nicht sein, dann passen andere sachen nicht. Dann passt z.b. 111011100 nicht.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2340
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-04-19


Das gleiche Problem wie bei q3 nochmal spiegelbildlich.



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

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Mit der Formulierung "der nur Eingaben akzeptiert, bei de[nen] [...]" wäre eigentlich auch ein Automat korrekt, der gar nichts akzeptiert.

Davon abgesehen ein Tipp für das wohl eigentlich gemeinte Problem: baue den Automaten, der (4 Zustände hat und) für alle Worte korrekt arbeitet, die nur aus 1en oder nur aus 0en bestehen.
Also z.B. 0, 00000, 000000000 sollen akzeptiert werden, aber $\varepsilon$, 00, 000, und 0000 nicht,
und z.B. 111, 1111111 sollen akzeptiert werden, aber $\varepsilon$, 1, 11 und 1111 nicht.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-04-20


Ja guter tipp, sehr sinnvoll nur auf 1en und 0en zu achten.

Hab es jetzt so, dürfte richtig sein:

    0   1
q0  q3  q1
q1  q0  q2
q2  q1  q3
q3  q2  q0

hab auch nicht mehr dran gedacht das sowas wie -5 mod 4 auch 3 ergibt (d.h. 5 Nullen). deswegen hats nie hingehauen.



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2018-04-20


Also ich hab hier noch eine aufgabe und zwar sollen wir einen DEA angeben der folgendes erfüllt:

{(01)^n | n >= 1} und
{(01)^n 1 | n >= 1}


Also er muss beides erfüllen. Weiß wer was das bedeutet? Das erste bedeutet denke ich, das der Automat alle Wörter mit Alphabet 0 und 1 akzeptieren muss, die mindestens 1 Zeichen lang sind. Aber was das 2. bedeutet weiß ich nicht, denn ich weiß nicht was diese 1 nach dem (01)^n bedeuten soll. Irgendjemand eine idee?



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


Was soll das heißen, dass der Automat zwei Mengen erfüllt?
Wie dem auch sei,
{(01)^n | n >= 1} ist m.E. die Menge der Wörter gerader Länge > 0, die mit 0 beginnen, und in denen 0 und 1 immer abwechselnd vorkommt. Also
    {01, 0101, 010101, 01010101...}
{(01)^n 1 | n >= 1} entsteht aus der ersten Menge, indem an jedes Element dieser rechts noch eine 1 angehangen wird. Also
    {011, 01011, 0101011, 010101011...}



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2018-04-20


Hmm weiß nicht was das heißt. In der Aufgabe steht eins zu eins:
DEA anlegen mit folgender Sprache:

{(01)^n | n >= 1} U {(01)^n 1 | n >= 1}

Wobei U ja denke ich das logische UND zeichen ist. Es ist auch wirklich ein U und kein v.

Und als nächste aufgabe, sollen wir den DEA so anpassen das er beide mengenteile auch für n>=0 akzeptiert.

den DEA für die erste menge hab ich, beim rest muss ich nochmal überlegen.



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

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
2018-04-20 22:23 - deskjet in Beitrag No. 14 schreibt:
Hmm weiß nicht was das heißt. In der Aufgabe steht eins zu eins:
DEA anlegen mit folgender Sprache:

{(01)^n | n >= 1} U {(01)^n 1 | n >= 1}
Ergibt schon mehr Sinn. Das U ist eigentlich ein $\cup$ und steht für die Vereinigung von Mengen. D.h. der Automat soll genau die Worte akzeptieren, die in einer der beiden Mengen enthalten sind. Mit anderen Worten: er soll alle Worte akzeptieren, die in der einen Menge drin sind, und alle, die in der anderen Menge drin sind, und sonst keine.

Wobei U ja denke ich das logische UND zeichen ist. Es ist auch wirklich ein U und kein v.
Das v wäre ein $\lor$, und stünde für oder. Zwischen Mengen ist das nicht angemessen.

Und als nächste aufgabe, sollen wir den DEA so anpassen das er beide mengenteile auch für n>=0 akzeptiert.

den DEA für die erste menge hab ich, beim rest muss ich nochmal überlegen.
Okay.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2018-04-20


Ah ok ja macht sinn. ich hab den DEA denke ich. Kann schlecht ein bild davon posten weil das Forum anscheinend nur 2,8kb große Dateien akzeptiert, aber auf jeden fall hab ich insgesamt 5 zustände, wobei ein zustand ein "fehlerzustand" ist, in dem man landet falls eine falsche eingabe kommt und aus dem zustand kommt man nicht mehr raus. Und ansonsten hab ich noch 3 endzustände (q0 , q2 und q3). q0 falls ein leeres wort eingelesen wird (für die zweite aufgabe mit n>=0) und q2 für (01)^n und q3 für (01)^n 1. Kann eigentlich nur stimmen.



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


Wenn dich eine Antwort interessiert, schreibe eine Tabelle auf (bzw. zwei: für jeden Automat eine). Was du gerade schrubst, ist kaum verständlich.  smile



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2018-04-21


Ok also folgendermaßen für das {(01)^n | n >= 1} U {(01)^n 1 | n >= 1}:

    0   1
q0  q1  qf
q1  qf  q2
q2  q1  q3
q3  qf  qf
qf  qf  qf

q2 und q3 sind Endzustand und q0 startzustand.

Falls der automat auch diese menge untersützen will:
{(01)^n | n >= 0} U {(01)^n 1 | n >= 0}
(also mit n >= 0)
Dann müsste einfach nur q0 noch zum endzustand werden. Denn n>=0 bedeutet denke ich nichts anderes als das auch noch das leere Wort akzeptiert werden muss.



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


2018-04-21 00:53 - deskjet in Beitrag No. 18 schreibt:
Ok also folgendermaßen für das {(01)^n | n >= 1} U {(01)^n 1 | n >= 1}:

    0   1
q0  q1  qf
q1  qf  q2
q2  q1  q3
q3  qf  qf
qf  qf  qf

q2 und q3 sind Endzustand und q0 startzustand.
Okay.

Falls der automat auch diese menge untersützen will:
{(01)^n | n >= 0} U {(01)^n 1 | n >= 0}
(also mit n >= 0)
Dann müsste einfach nur q0 noch zum endzustand werden. Denn n>=0 bedeutet denke ich nichts anderes als das auch noch das leere Wort akzeptiert werden muss.
Der Automat wäre falsch. Ich verrate nicht, wieso, denn dann wär's zu einfach.  razz Überlege nochmal ganz langsam und genau, welche Worte in {(01)^n | n >= 0} U {(01)^n 1 | n >= 0} enthalten sind.



  Profil  Quote  Link auf diesen Beitrag Link
deskjet
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.11.2016
Mitteilungen: 36
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2018-04-21


Ich würd sagen in {(01)^n | n >= 0} ist das leere Wort, 01, 010101, etc. enthalten und in {(01)^n 1 | n >= 0} ist 1, 011, 01011, etc. enthalten. 1 deswegen, weil (01)^0 das leere Wort ist, und daran wird noch eine 1 drangehängt. D.h. der automat muss vom startzustand mit einer 1 direkt in den endzustand kommen müssen.

Damit säh der automat dann so aus:

    0  1
q0  q1 q4
q1  qf q2
q2  q1 q3
q3  qf qf
q4  qf qf
qf  qf qf

q0, q2, q3 und q4 sind endzustand und q0 erstzustand.



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


Gut. Der Automat funktioniert. Man kommt aber auch mit einem Zustand weniger aus.



  Profil  Quote  Link auf diesen Beitrag Link
deskjet 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]