Laboratorijske vježbe

1. Zadatak

Programski ostvariti generator i simulator konačnog automata za upravljanje radom semafora na pješačkom prijelazu prema slici 1. Sustav semafora za regulaciju prometa na pješačkom prijelazu sastoji se od semafora za automobile i semafora za pješake. Semafori za automobile sastoje se od crvenog, žutog i zelenog svjetla, dok se semafori za pješake sastoje od crvenog i zelenog svjetla. Tijekom rada, semafori rade u ciklusu koji je prikazan tablicom 1.

Slika 1. Sustav semafora upravljan konačnim automatom

Tablica 1. Ciklus rada semafora

Semafori su opremljeni senzorima za praćenje dolaska pješaka i automobila i rade u sljedećem režimu:

• zeleno svjetlo na semaforu za automobile traje minimalno T_AZmin sekundi, a maksimalno T_AZmax sekundi

• zeleno svjetlo na semaforu za pješake traje minimalno T_PZmin sekundi, a maksimalno T_PZmax sekundi

• ako se na semaforu za pješake okupi minimalno N_P pješaka prije isteka vremena T_AZmax, pokreće se izmjena stanja semafora u korist pješaka

• ako se na semaforu za automobile okupi minimalno N_A automobila prije isteka vremena T_PZmax, pokreće se izmjena stanja semafora u korist automobila

• crveno+žuto svjetlo na semaforu za automobile traje T_ACŽ sekundi

• žuto svjetlo na semaforu za automobile traje T_AŽ sekundi

• crveno svjetlo istovremeno na oba semafora traje T_ACPC sekundi

Napisati program za generiranje konačnog automata za upravljanje radom semafora prema zadanom režimu. Vrijednosti T_AZmin, T_AZmax, T_PZmin, T_PZmax, N_P, N_A, T_ACŽ, T_AŽ i T_ACPC su parametri za generiranje automata i zadaju se prilikom pokretanja programa.

Ulaznu abecedu automata čine znakovi P, A i S. Značenje znakova je sljedeće:

• P - novi pješak je pristigao na semafor za pješake

• A - novi automobil je pristigao na semafor za automobile

• S - protekla je 1 sekunda od prethodnog slanja znaka S

Može se zamisliti da znakovi P i A dolaze od senzora za praćenje dolaska pješaka i automobila, a znak S svake sekunde od sata.

Izlaz automata u svakom trenutku trebaju biti dvije informacije:

• upaljeno svjetlo na semaforu za automobile

• upaljeno svjetlo na semaforu za pješake

Može se zamisliti da je izlaz konačnog automata spojen na odgovarajuće prekidače koji pale žarulje na semaforima.

Dodatne pretpostavke kod rješavanja zadatka:

• pješaci i automobili dolaze proizvoljnom dinamikom, za vrijeme bilo koje kombinacije svjetala na semaforima

• ako automobil ili pješak naiđe na zeleno svjetlo na semaforu, trenutačno prolazi kroz semafor (ne troši vrijeme ni prostor)

• svi pješaci ili automobili koji su prethodno bili zaustavljeni na crvenom svjetlu na semaforu, u trenutku paljenja zelenog svjetla trenutačno prolaze kroz semafor bez obzira na duljinu nagomilanog reda (neposredno nakon gašenja zelenog svjetla, nitko ne čeka na taj semafor)

• nije bitno s koje strane semafora nailaze automobili i pješaci (parametri N_A i N_P promatraju se kao ukupni broj automobila, odnosno pješaka s obje strane semafora)

• početno stanje prometnog sustava:

  • početno stanje semafora je prvi redak u tablici 1 (crvena svjetla na oba semafora), nakon čega se semafor pali u korist automobila

  • još nema nijednog pristiglog automobila ni pješaka

• promjene stanja semafora uvijek se događaju sinkrono sa signalom sata (nakon primljenog odgovarajućeg broja znakova S). To ujedno znači da će promjena stanja semafora uzrokovana prekoračenjem kritičnog broja automobila ili pješaka nastupiti sinkrono sa sljedećim signalom sata (pod uvjetom da je proteklo barem T_AZmin, odnosno T_PZmin sekundi), a ne neposredno nakon što se dosegne kritični broj automobila ili pješaka koji čekaju na semafor

Generirani konačni automat OBVEZNO zapisati u izlaznu datoteku. Format zapisa definicije automata je proizvoljan.

Programski ostvariti simulator konačnog automata koji:

• iz datoteke učitava definiciju konačnog automata dobivenu iz generatora

• od korisnika učitava proizvoljan broj ulaznih nizova

• ispisuje izlaz automata na zaslon računala

Shema povezivanja generatora i simulatora prikazana je slikom 2.

Slika 2. Shema povezivanja generatora i simulatora konačnog automata

Funkcija prijelaza Turingovog stroja zadaje se ulaznom datotekom. U prvom retku datoteke zapisana je oznaka početnog stanja. Prijelazi se zapisuju prema sljedećem formatu:

stanje#znak_na_traci#novo_stanje#novi_znak_na_traci#smjer_pomaka_glave

Oznake stanja mogu biti proizvoljni nizovi znakova. Za znakove trake koriste se pojedinačni znakovi. Prazna ćelija označava se oznakom B. Smjerovi pomaka glave su D za pomak u desno, odnosno L za pomak u lijevo. Primjer datoteke s funkcijom prijelaza (primjer 4.1 u udžbeniku):

0

0#0#1#X#D

1#0#1#0#D

2#0#2#0#L

1#1#2#Y#L

2#X#0#X#D

0#Y#3#Y#D

1#Y#1#Y#D

2#Y#2#Y#L

3#Y#3#Y#D

3#B#4#B#D