Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Nemdeterminisztikus automata megadás?

27
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
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