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

Doplněk regulárního jazyka

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áme regulární jazyk L. Dokážeme, že doplněk jazyka L je opět regulární jazyk.

Co je to doplněk #

Doplňkem jazyka L rozumíme všechna slova, která nejsou v jazyku L. Doplněk značíme L Tj. pro abecedu \(\Sigma\) platí, že:

\[L’ = \left\{w \in \Sigma^\ast\,|\, w \notin L\right\}.\]

Například pro jazyk slov obsahujících alespoň jeden symbol 1 by doplněk byl jazyk, kter obsahuje slova, která neobsahují ani jeden symbol 1.

Postup #

Postup je velice jednoduchý. Máme regulární jazyk L a automat \(A=\left< Q, \Sigma, \delta, q_0, F\right>\), který ho přojímá. Automat A, který přijímá L sestrojíme tak, že prohodíme koncové a nekoncové stavy: \(A’=\left< Q, \Sigma, \delta, q_0, Q\setminus F\right>\). To je celé.

Příklad #

Mějme tento automat:

Automat přijímající doplněk jazyka by vypadal takto:

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