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

Uzavřenost 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

Jazyk L je regulární, právě tehdy, pokud existuje automat A, který tento jazyk přijímá, tj. L(A) = L. Dokážeme si, že regulární jazyky jsou uzavřené na operacích sjednocení, průnik, konkatenace a uzávěr.

Uzavřenost na množině vzhledem k operaci #

Řekneme, že množina M je uzavřena na operaci \(\otimes\) pokud platí, že

\[\forall x, y \in M: x \otimes y \in M\]

Příkladem je například operace sčítání na množině přirozených čísel. Součet jakýchkoliv dvou přirozených čísel je opět přirozené číslo. Naopak množina přirozených čísel není uzvařená na odečítání, protože například 7 − 15 = −8 a číslo −8 není přirozené.

Dokážeme si, vůči kterým operacím je uzavřena množina regulární jazyků. Všechny důkazy budou konstrukční, tj. sestrojíme automat, který přijímá výsledný jazyk.

 

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