PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Rozdíl regulárních jazyků

Zobrazit kapitoly článku
  1. Uzavřenost regulárních jazyků
  2. Sjednocení
  3. Průnik
  4. Rozdíl
  5. Doplněk
  6. Zřetězení
  7. Uzávěr

Mějme dva regulární jazyky L1, L2. Dokážeme, že jejich rozdíl \(L = L_1 \setminus L_2\) je také regulární jazyk.

Idea #

Ve skutečnosti není moc co dokazovat. Pro rozdíl dvou množin totiž platí následující vztah:

\[L_1 \setminus L_2 = L_1 \cap L_2^\prime,\]

kde \(L_2^\prime\) je doplněk jazyka L2. Z kapitol o průniku regulárních jazyků a doplňku regulárních víme, že regulární jazyky jsou na obě tyto operace uzavřené. To znamená, že dokážeme sestrojit automat, který přijímá průnik jazyků a doplněk jazyku. Tyto automaty tak můžeme použít k sestrojení automatu, který bude přijímat jazyk \(L_1 \cap L_2^\prime\), což je ale zároveň jazyk \(L_1 \setminus L_2\).

Příklad #

Mějme tento automat A1, který přijímá všechna slova, která obsahují sudý počet 1:

a automat A2, který příjmá slova obsahující lichý počet 0:

Sestrojíme automat, který bude přijímat rozdíl těchto jazyků. Potřebujeme tak automat \(A_2^\prime\), který bude doplňkem k automatu A2. Jen prohodíme koncové a nekoncové stavy:

Teď už jen sestrojíme automat A, který bude přijímat průnik jazyků L(A1) a \(L(A_2^\prime)\):

Zdroje #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace