Sjednocení
Výsledný automat přijímá jazyk L, kde L = L1 ∪ L2. Zkonstruovat automat přijímající sjednocení jazyků můžeme třemi způsoby: - ε-přechody - automat s více počítečními stavy - paralelní činnost automatů.
Průnik
- paralelní činnost automatů.
Algoritmus je v podstatě stejný jako v případě sjednocení. Rozdílné bude určení koncových stavů. Nyní budou ve výsledném automatu koncové ty stavy, které obsahují koncový stav z obou vstupních automatů zároveň.
Doplněk
Vstupem musí být deterministický úplně určený automat M.
Následně u automatu M prohodíme koncové a nekoncové stavy a získáme tak automat M'.
Rozdíl
Jde o případ průniku automatu M1 a doplňkem M2.
Součin
- Ze všech koncových stavů automatu M1 vedeme ε-přechody do počátečního stavu automatu M2.
- Koncové stavy automatu M1 již nebudou koncové a počáteční stavy M2 již nebudou počáteční
Iterace
- Přidáme počáteční stav, který bude zároveň koncový. U původního počátečního stavu tento příznak zrušíme.
- Z nového počátečního stavu vedeme ε-přechod do původního počátečního stavu
- Ze všech koncových stavů (kromě nově přidaného počátečního stavu) vedeme ε-přechody do původního počátečního stavu.