Definice .

Přechodovým grafem nazveme čtveřici , kde:

 
• Q je konečná množina stavů
• je počáteční stav ( značí nedefinovaný stav)
• Act je množina akcí (viz předch. definice)
• je konečná přechodová relace, zapisujeme