PSD 2014: Informatika je tudi znanost - formalni jeziki in avtomati

Zapiši besede

Za na sliki prikazan diagram prehodov ugotovi naslednje.

a) Zapiši zaporedja črk (besede), ki pripeljejo iz začetnega stanja v končno.

b) Kam pripelje beseda hilna?

c) Kam pripelje beseda hitra?

Neznani diagram prehodov

Za na sliki prikazan diagram prehodov ugotovi naslednje.

a) Koliko stanj ima diagram?

b) Koliko prehodov ima diagram?

c) Kateri prehodi so enosmerni in kateri dvosmerni?

d) Katera stanja so začetna?

e) Katera stanja so končna?

f) Za naslednja zaporedja prehodov ugotovi ali pripeljejo v končno stanje ali ne?

• a
• b
• aabb
• abbbbaaaab
• bbbaaabbbaaa
• abababababab
• abaabaabaabaabaababa

g) Zapiši vsaj dve zaporedji, ki pripeljejo v stanje

• q0
• q1
• q2
• q3
• q4
• q5