03 Homogenní konečný automat
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Homogenní konečný automat
- $M = (Q, \Sigma, \delta, q_{0}, F)$ a $Q(a)$ jsou množiny cílových stavů $\forall a \in \Sigma$
- Jestliže pro všechny dvojice symbolů $a,b \in \Sigma, a \neq b$, platí $Q(a) \cap Q(b) = \emptyset$, pak se automat nazývá homogenní
- Množiny cílových stavů mají prázdný průnik
- Tedy když do každého stavu vedou přechody označeny pouze jediným písmenem
- Množiny cílových stavů nám tvoří tzv. rozklad, tedy když je sjednotím, vznikne množina všech stavů
- Pokud $M$ je homogenní NKA, pak počet stavů DKA $M’$ získaného standardní [determinizací](notes/bi-aag/02-nedeterministicky-konecny-automat.md#Převod NKA na DKA determinizace) (podmnožinovou konstrukcí) je omezen vztahem níže, tedy $< 2^{n}$ $$ |Q’| \leq \sum_{a \in \Sigma}{(2^{Q(a)})-|\Sigma|+1} $$