Glenn wrote:Fristi wrote:Ik ga ff mierenneuken:
Dit moet eignelijk in het subforum voor 1ste bach staan
Wij (zijnde de ouderejaars) lezen daar ook dus geen vrees dat je topic zal verdwijnen in het niets, wij kijken dat ook na
Sorry dat ik dit bericht op het verkeerde forum heb gepost. Het was normaal gezien de bedoeling om dit op het forum van de eerste bachelor te plaatsen maar ik zal me vergist hebben. Verplaats dit bericht maar naar het forum waar het thuishoort
.
Pieter Belmans wrote:Je wil een DFA tekenen, die _moet_ bij elke staat transities op elk symbool hebben.
Als je 1 staat hebt, kan je maar op 1 manier uit de startstaat (die dan ook eindstaat is) twee transities tekenen, namelijk naar zichzelf.
Als je 2 staten hebt, kan je enkele configuraties maken (afhanekelijk van of je de eindstaat wil bereiken of niet, indien niet heb je dus meer mogelijkheden) maar zeker geen 64
.
Allereerst hartelijk dank voor je antwoord Pieter
.
Ik heb de opdracht bij 2 staten nu gemaakt en ik kom nu op 16 mogelijkheden (dat is toch wel wat minder dan die 64
). Maar bij de opdracht voor één staat kom ik wel op vier transitiediagrammen (zie afbeelding). Ik weet nu wel niet of dit juist is.
ps: de voorbeelden die ik erbij heb geschreven zijn voorbeelden van mogelijke strings.
Die eerste automaat aanvaardt geen enkele string, vanaf er 1 symbool wordt ingelezen gaat hij in de niet-getekende vuilbakstaat.
De tweede en derde automaat zijn geen DFA's maar NFA's, die wederom geen vuilbakstaat bevatten (maar dat hoeft niet per se).
Enkel de vierde is een geldige automaat. Die de string die jij daar beschrijft aanvaardt. Je kan, als je houdt van geavanceerdere informatica, nadenken over hoeveel informatie een automaat kan opslaan, en in 1 staat valt vrij weinig op te slaan, dus kan je weinig invloed hebben op de aanvaardde strings
.
De strings die je aanvaardt in 2 en 3 kunnen wel aanvaard worden, maar enkel in een automaat met (minstens) 2 staten, omdat je moet bijhouden of er al een van de "slechte" karakters is ingelezen en hiervoor heb je dus meer staten nodig. Die tweede en derde ga je dus tekenen met een startstaat (die ook beginstaat is), en een transitie van de beginstaat naar de tweede (= garbagestaat) op het karakter dat je niet wil dat ingelezen wordt. De beginstaat heeft een lus op het wel gewenste karakter en op de garbagestaat zit er een lus op beide karakters (omdat je niet wil dat er vanaf 1 slecht karakter nog iets aanvaard wordt).
De andere mogelijkheid die er is, zijn strings à la xyxy en yxyx. Ofwel met een even ofwel een oneven aantal symbolen.
Vergeet je beginpijlen trouwens niet te tekenen, nu heb je een automaat die zelfs de lege string niet aanvaardt, de
.
Van Lorenz' ASCII schema's begrijp ik trouwens geen hol
.