Keresés


Toplista

Toplista
  • betöltés...

Magántanár kereső

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?

312
A feladat hogy adjon meg ezeket a nyelveket felismerő véges nemdeterminisztikus automatákat, majd determinizálja őket.

https://kepkuldes.com/image/eQmRQV

É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 :D
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
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.
1