Alternirajući automati

Opis projektnog zadatka:

Cilj ovog projektnog zadatka je izraditi implementaciju osnovnih algoritama vezanih uz alternirajuće konačne automate. Konkretno, potrebno je implementirati slijedeće funkcije:

• Provjera prihvaćanja ulazne riječi od strane alternirajućeg automata
• Provjera nepraznosti jezika alternirajućeg automata
• Provjera univerzalnosti jezika alternirajućeg automata
• Nalaženje najkraćeg svjedoka nepraznosti jezika (tj. najkraće prihvaćene riječi) alternirajućeg automata
• Osnovne operacije nad jezicima alternirajućih automata: unija, presjek, komplement, konkatenacija, iteracija, testiranje jednakosti
• Konverzija alternirajućeg u nedeterministički konačni automat

Potrebno je dobro osmisliti pogodan način interne reprezentacije alternirajućeg automata, te, u dogovoru s asistentom, definirati (poželjno XML-baziran) format ulazno-izlaznih datoteka. Sva implementacija treba biti napravljena u jeziku C++ ili C#.

Reference:

1. S. Yu: Regular languages, Handbook of Formal Languages, Vol 1, 1997, 41-110.
2. M. Vardi: An automata-theoretic approach to linear temporal logic, Banff'94. (sekcije 2.1, 2.3 i 2.5)

Opcionalni dio zadatka: Implementacija alternirajućih konačnih automata s epsilon-prijelazima.

Projektni zadatak sastavio: Matko Botinčan.