this dir | view | cards | source | edit | dark
top
- rozdíly v definici automatu
- někdy je požadována totální přechodová funkce
- vyřešíme přidáním stavu fail
- někdy je požadovaný počáteční stav
- vyřešíme přidáním stavu final
- iterační (pumping) lemma pro regulární jazyky
- (∀L∈L3)(∃n∈N)(∀w∈L,∣w∣≥n):w=xyz
- y=ϵ
- ∣xy∣≤n
- ∀k∈N0: slovo xykz je také v L
- tzn. w lze rozdělit na tři části, kde druhá je neprázdná, první dvě jsou krátké a druhou lze libovolně iterovat
- důkaz z principu holubníku (mám delší slovo než je počet stavů → nějaký stav se musí opakovat)
- součin automatů
- trik, který lze použít pro sestavení automatu pro jazyk s konjunkcí podmínek