Pretvorbe med NKA in DKA

Naloga 1.

a) Za podani NKA zapišite potenčno množico njegovih stanj. Katere podmnožice predstavljajo končno stanje v DKA?

b)  Podani NKA transformirajte v DKA

c) Koliko stanj iz potenčne množice je dejansko uporabljenih?

d) Z besedami opišite kakšen jezik ta avtomat razpoznava.

d) Zamislite si NKA s dvemi stanji, ki pri pretvorbi v DKA uporabi vsa stanja iz potenčne množice njegovih stanj.

Naloga 2.

Podan imate jezik vseh besed sestavljenih iz črk a in b, ki so bodisi sode dolžine bodisi je njihova dolžina manjša od 4.

a) Za ta jezik najprej zapišite nekaj besed, ki pripadajo temu jeziku in

b)  nekaj besed, ki temu jeziku ne pripadajo.

c) Zapišite nedeterministični končni avtomat za ta jezik.

d) Pretvorite zapisani avtomat v determinističnega. Pri tem ne uporabite tabele, ampak zapišite samo tista stanja, ki so dosegljiva iz začetnega stanja. 

Naloga 3.

V človeškem genomu bi radi poiskali vzorec AGAGA. Abeceda je torej sestavljena iz znakov C, T, G, A.

a) Zapišite ta vzorec kot NKA.

b) Pretvorite zapisani avtomat v DKA.  

c) S tako dobljenim avtomatom načeloma lahko zgolj povem ali je vzorec prisoten v nekem nizu.  Če avtomatu dodam možnost izpisa znaka na izhod, lahko tudi prešteje kolikokrat se nek vzorec v nizu nahaja. V katerih stanjih moramo dodati izpis, da bo avtomat štel pojavitve vzorca?

Naloga 4.

Zapišite nedeterministični končni avtomat nad abecedo Σ={1,2}, ki sprejme vse nize, ki se končajo na znak, ki se je v nizu že enkrat pojavil.

Npr., če se niz konča na 1, potem se je morala enica že enkrat pojaviti v nizu (enako velja za znak 2 ).

a) Koliko stanj ima NKA?

b) Pretvorite NKA v DKA z razširjanjem stanj. Koliko stanj ima DKA? 

c) Koliko stanj iz potenčne množice stanj NKA-ja je nedosegljivih?

*Naloga 5.

Napišite program v pythonu, ki pretvori podani nedeterministični avtomat v deterministični avtomat.