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

Průnik 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 průnik \(L = L_1 \cap L_2\) je také regulární jazyk.

Idea důkazu #

Máme dva regulární jazyky L1 a L2 a chceme dokázat, že jejich průnik \(L_1 \cap L_2\) je opět regulární jazyk. Protože L1 a L2 jsou regulární jazyky, tak existují konečné automaty A1 a A2, které přijímají jazyky L1 a L2, tedy platí L(A1) = L1 a L(A2) = L2. My dále sestavíme konečný automat A, který bude přijímat jazyk \(L_1 \cap L_2\), čímž dokážeme, že jazyk \(L_1 \cap L_2\) je regulární.

Slovo patří do průniku jazyků, pokud patří do jazyka L1 a zároveň L2. Tedy slovo musí přijímat automat A1 a zároveň automat A2. Využijeme úplně stejnou ideu, jakou jsme využili u sjednocení regulárních jazyků, pouze změníme množinu koncových stavů.

Formalizace postupu. #

Máme dva automaty,

\begin{eqnarray} A_1&=&\left< Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left< Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Sestrojíme automat \(A=\left< Q, \Sigma, \delta, q, F\right>\), který přijímá jazyk \(L(A_1)\cap L(A_2)\). Platí, že

  • \(Q = Q_1 \times Q_2\)
  • \(\Sigma = \Sigma_1 \cap \Sigma_2\)
  • \(q = \left< q_0, p_0\right>\)
  • \(F = F_1 \times F_2\)

Pro přechodovou funkci δ bude platit následující vztah:

\[\forall q\in Q_1, p\in Q_2: \delta(\left< q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right>\]

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 průnik těchto jazyků. Množina stavů tohoto automatu má tvar \(Q = Q_1 \times Q_2\), počáteční stav je stav \(\left< q_0, p_0\right>\) a koncové stavy jsou \(F_1 \times F_2\):

Dále dotvoříme přechody tak, že \(\delta(\left< q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right>\):

V tomto automatu je například ze stavu \(\left< q_0, p_0\right>\) přechod pro symbol 0 do stavu \(\left< q_0,p_1\right>\). Znamená to, že automat A1 má ze stavu q0 přechod pro symbol 0 zpět do stavu q0. Automat A2 má zase pro symbol 0 přechod ze stavu p0 do stavu p1.

Automat si můžeme vyzkoušet. Měl by přijímat slova jako 110 nebo 00000 (obsahují sudý počet 1 a zároveň lichý počet 0), ale neměl by přijímat slova jako 11, 111, 1010).

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