Naloge iz nedeterminističnih končnih avtomatov

Naloga 1.

Na sliki imate podan končni avtomat. Odgovorite na naslednja vprašanja:

a) Kje lahko vidite, da gre za nedeterministični avtomat?

b) Zapišite nekaj besed, ki jih ta avtomat sprejema.

c) Zapišite nekaj besed, ki jih ta avtomat ne sprejema.

d) Zapišite izvajanje avtomata na besedi baaaa.

e) Na koliko različnih načinov lahko avtomat to besedo sprejme?

Naloga 2.

a) Za zgornji nedeterministični avtomat zapišite drevo izvajanja na besedi aaa.

b) Na koliko različnih načinov lahko ta avtomat sprejme besedo dolžine n?

c) Denimo, da prehode iz enega stanja po istem simbolu še posebej označimo. Če gre avtomat po simbolu a v isto stanje, potem to označimo z 0, če pa gre v drugo stanje, potem to označimo z 1. En niz ničel in enic nam v drevesu izvajanja podaja enolično pot, po kateri se je avtomat sprehodil.  Kakšno je zaporedje stanj (v katerih se je ta avtomat nahajal), če imamo pot označeno z nizom 00100111?

d) Narišite avtomat, ki besedo dolžine n lahko sprejme na 4n načinov.

Naloga 3.

Nedeterminizem je ena izmed možnih razširitev determinističnih končnih avtomatov. Končnim avtomatom lahko dodamo še številne druge razširitve. Ena možna razširitev je, da se lahko avtomat po vhodni besedi sprehaja tako desno kot tudi levo (dostopa lahko tud do znakov, ki jih je že videl).

a) Zapišite formalno definicijo takih dvosmernih avtomatov - predvsem razmislite o funkciji prehodov.

b) Kdaj naj ta avtomat besedo sprejme?

c) Narišite en enostaven  dvosmerni avtomat (lahko je za povsem sintetičen jezik, samo da vsebuje premike tako levo kot desno).

Naloga 4.

V JFlap-u sestavite avtomat za jezik vseh besed sestavljenih iz črk a in b, ki imajo sodo dolžino ali pa vsebujejo največ 4 a-je.

Izvajajte avtomat na nekaj besedah, ki pripadajo temu jeziku, in nekaj besedah, ki jih v tem jeziku ni.

Naloga 5.*

Spremenite program za simulacijo nedeterminističnih avtomatov tako, da namesto množic uporabite sezname (iz katerih ne odstranjujete duplikatov).  Preizkusite kako deluje avtomat, ki ste ga razvili v nalogi 2.