Množinové operace nad regulárními jazyky (konečnými automaty)

Jelikož jazyk (i ten regulární) je v podstatě množina slov, můžeme nad ním dělat klasické množinové operace. A protože pro každý regulární jazyk existuje konečný automat, můžeme tyto množinové operace aplikovat i na konečné automaty.

Následující příklady jsou popsány na regulárních jazycích:

LA - obsahuje slova nad abecedou {a,b} se sudým počtem áček. Je dán konečným automatem A (na obrázku vlevo).
LB - obsahuje slova nad abecedou {a,b} které obsahují pouze áčka. Je dán konečným automatem B (na obrazku vpravo).

Doplněk

Převedení konečného automatu A na automat A', jehož regulární jazyk L'(A') je doplňkem jazyku jazyku L(A) je jednoduchý. Stačí invertovat koncové stavy. Tedy všechny stavy které u automatu A nebyly koncové u automatu A' koncové budou a ty které koncové byly, v doplňkovém automatu zas nebudou. Pak logicky všechny slova které jeden automat příjme, druhý nepřijme, což je podstata doplňku.

Doplňkový automat A' k automatu A, bude mít koncový stav A2 a stav A1 koncový nebude. Stejně tak u automatu B. B' má stav B2 koncový a B1 nekoncový.

Sjednocení a průnik 

Automat vzniklý sjednocením nebo průnikem dvou automatů se liší pouze v koncových stavech jinak je postup stejny.

  1. Procházím oběma automaty zároveň a vytvářím nový automat tak, že stav nového automatu vznikne ze dvou stavů těch původních. Pro automaty A, B definované výše postupuji nasledovně:
    • začínám ve stavu A1B1. Kam se z počátečního stavu dostanu v případě symbolu 'a'? Ze stavu A1 -a-> A2 a ze stavu B1 -a-> B1. V případě symbolu 'b': A1 -b-> A1, B1 -b-> B2
    • Vytvořím nový stav A2B2 a propojím jej hranou označenou 'a' z počátečního stavu A1B1.
    • Vytvořím nový stav A1B1 a propojíme jej hranou b z počatečního stavu A1B1.
    • Tak pokračuji dál, dokud nemám celý graf jak jej vidíme na obrázku.
  2. Nyní se můžu rozhodnou zda chceme průnik či sjednocení, podle toho označíme stavy vytvořeného automatu.
    • Průnik A ∩ B - koncové stavy jsou A1B1. Hledám stav který je koncový u původního automatu A a zároveň automatu B.
    • Sjednocení A  ∪ B - koncové stavy jsou A1B1, A1B2 a A2B1. Protože hledám stavy které jsou koncové buď u atomatu A nebo B.