Ändlig automat

Ändliga automater eller finita automater är en beräkningsmodell som används inom datavetenskap. Automaten består av ett (ändligt) alfabet, en ändlig mängd av tillstånd samt övergångar mellan tillstånden. Ett av tillstånden är starttillstånd och en delmängd av tillståndsmängden är accepterande sluttillstånd.

Det vill säga alla reguljära uttryck kan beskrivas som ändliga automater och alla ändliga automater kan skrivas som reguljära uttryck.

Deterministisk ändlig automat

Icke-deterministisk ändlig automat

• Tillståndsmaskin