Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Nemdeterminisztikus automata megadás?
Márk462
kérdése
312
A feladat hogy adjon meg ezeket a nyelveket felismerő véges nemdeterminisztikus automatákat, majd determinizálja őket.
Én így oldottam meg őket,viszont nem tudom, hogy jók-e, mert ha JFlap-ben determinizálom őket akkor is mást kapok meg ha papíron táblázatban csinálom akkor is és ebből gondolom , hogy akkor valőszínű, hogy ez nem jó megoldás https://kepkuldes.com/image/eQm4GN https://kepkuldes.com/image/eQmX7q
Jelenleg 1 felhasználó nézi ezt a kérdést.
automata, nemdeterminisztikus, nyelv
0
Felsőoktatás / Matematika
Válaszok
1
AlBundy{ Polihisztor }
megoldása
Nézzük az elsőt. A kiindulási NFA nem jó. Egyrészt a végállapotban ha `a`-t olvas, akkor ott kéne maradnia, a tied viszont leáll, emiatt például az `aaaaa` szót nem fogadja el (feltételezem, hogy a "három darab `a`-ra végződik" azt jelenti, hogy az utolsó három karaktere `a`, nem pedig azt, hogy pontosan három `a` van a végén). Másrészt a q1 és a q3 állapotokban `b` és `c` hatására szintén leáll, pedig azt még nyugodtan követhetné három `a`, tehát például az `aabaaa` szót sem fogadja el. De fölöslegesen bonyolult is az NFA: 4 állapottal is megoldható a dolog, így ha papíron determinizálsz, a hatványhalmazod 32 helyett csak 16 állapotú lesz. Mellesleg ehhez viszonylag triviális egyből DFA-t rajzolni: ha bármelyik állapotban `a`-tól különböző bemenetet olvasunk, akkor megyünk vissza a kiindulási állapotba. Lásd az első mellékelt képet: felül az NFA, alul a DFA, JFLAP szerint ekvivalensek.
A másodiknál az üres szavas átmenet fölösleges, egyébként jó az NFA. Mellékeltem ehhez is képet, alul a DFA. Nem determinizáltam, hanem közvetlenül felrajzoltam ezt is.