04.7 Převod gramatika-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}}
$$
# Převod gramatika-automat
Převod regul. gram. na DKA
- To, co jsou v gramatice terminální symboly, budou v automatu stavy (+ přibyde 1 koncový stav)
- Kdykoliv v gramatice bude pravidlo ve tvaru $N \rightarrow TN$ (např. $B \rightarrow aC$), do automatu přidám přechod $a$ ze stavu $B$ do stavu $C$
- Kdykoliv v gramatice bude pravidlo ve tvaru $N \rightarrow T$ (např. $B \rightarrow a$), do automatu přidám přechod $a$ ze stavu $B$ do koncového stavu
Převod NKA na regul. gram.
- (NKA musí být s jedním počátečním stavem bez $\varepsilon$ přechodů)
- Startovací symbol gramatiky je počáteční stav automatu
- Když mám přechod ze stavu $B$ do $C$ přes symbol $a$, zapíšu pravidlo $B \rightarrow aC$
- Když mám přechod ze stavu $B$ do koncového $A$ přes symbol $d$, přidám ještě pravidlo $B \rightarrow dA , | , d$
- Pokud je počáteční zároveň koncový
- $S$ není na pravé straně žádného z pravidel - můžu přidat pravidlo $S \rightarrow \varepsilon$
- $S$ je na pravé straně nějakého z pravidel - přidám nový startovací symbol gramatiky $S’$, pravidlo $S’ \rightarrow \varepsilon$, a zároveň do něj přidám všechny pravidla vycházející z $S$