Slovník pojmů (ve vývoji)



Currently sorted By last update ascending Sort chronologically: By last update change to descending | By creation date

Page:  1  2  3  4  (Next)
  ALL

Postův korespondenční problém

Instance \pojem{Postova korespondenčního problému (PCP)} jsou dva seznamy slov nad abecedou $\Sigma$ značené $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$ stejné délky $k$. Pro každé $i$, dvojice $(w_i,x_i) $ se nazývá \pojem{odpovídající} dvojice.

Instance PCP \pojem{má řešení}, pokud existuje posloupnost jednoho či více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že $w_{i_1}, w_{i_2}, \ldots, w_{i_m}=x_{i_1}, x_{i_2}, \ldots, x_{i_m} $ tj. dostaneme stejné slovo.
V tom případě říkáme, že posloupnost ${i_1}, {i_2}, \ldots, {i_m}$  \pojem{je řešení}.

\pojem{Postův korespondenční problém} je: Pro danou instanci PCP, rozhodněte, zda má řešení.


deterministický konečný automat

Deterministický konečný automat (DFA) A = (Q,Σ,δ,q0 ,F) sestává z:
konečné množiny stavů, zpravidla značíme Q
konečné množiny vstupních symbolů, značíme Σ
přechodové funkce, zobrazení z Q × Σ → Q, značíme δ, která bude
reprezentovaná hranami grafu
počátečního stavu q0 ∈ Q, vede do něj šipka ’odnikud’,
a množiny koncových (přijímajících) stavů (final states) F ⊆ Q,
označených dvojitým kruhem či šipkou ’ven’.


Lineárně omezené automaty

\pojem{Lineárně omezený automat LBA} je nedeterministický TM, kde na pásce je označen levý a pravý konec $\underline{l},\underline{r}$. Tyto symboly nelze při výpočtu přepsat a nesmí se jít nalevo od $\underline{l}$ a napravo od $\underline{r}$.

Slovo $w$ \pojem{je přijímáno lineárně omezeným automatem}, pokud $q_0\underline{l}w\underline{r}\vdash^*\alpha p\beta$, $p\in F$.


Modifikovaný Postův korespondenční probém

Mějme PCP, tj. seznamy $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$. Hledáme seznam 0 nebo více přirozených čísel  ${i_1}, {i_2}, \ldots, {i_m}$ tak že ${\bf w_1,}w_{i_1}, w_{i_2}, \ldots, w_{i_m}={\bf x_1,}x_{i_1}, x_{i_2}, \ldots, x_{i_m} $. V tom případě říkáme, že PCP \pojem{má iniciální řešení}.

\pojem{Modifikovaný Postův korespondenční problém}: má PCP iniciální řešení?


Postova věta

Jazyk $L$ je rekurzivní, právě když $L$ i $\overline{L}$ (doplněk) jsou rekurzivně spočetné.


Rekurzivní jazyky

Říkáme, že TM rozhoduje jazyk L, pokud L=L(M) a pro každé $w$ stroj nad w zastaví.

Jazyky rozhodnutelné TM nazýváme rekurzivní jazyky.


regulární jazyky

Jazyky přijímané konečnými automaty.

 

Alternativně (Kleene): Nejmenší třída jazyků, která obsahuje prázdný jazyk, jazyk pro každé písmeno abecedy Sigma a je uzavřená na sjednocení, zřetězení a iteraci.


Myhill--Nerodova věta

Nechť $L$ je jazyk nad konečnou abecedou $\Sigma$. Potom následující tvrzení jsou ekvivalentní:
\begin{itemize}
 \item[a)] $L$ je rozpoznatelný konečným automatem,
 \item[b)] existuje pravá kongruence $\sim$ konečného indexu nad $\sigma^*$ tak, že $L$ je sjednocením jistých tříd rozkladu $\Sigma^*/\sim$.
\end{itemize}


Nalezení reduktu deterministického konečného automatu

 \item Ze vstupního DFA $A$ eliminujeme stavy nedosažitelné z počátečního stavu.
\item Najdeme rozklad zbylých stavů na třídy ekvivalence.
\item Konstruujeme DFA $B$ na třídách ekvivalence jakožto stavech. Přechodovou funkci $B$ označíme $\gamma$, mějme $S\in Q_B$. Pro libovolné $q\in S$, označíme $T$ třídu ekvivalence $\delta(q,a)$ a definujeme $\gamma(S,a)=T$. Tato třída musí být stejná pro všechna $a \in S$.
\item Počáteční stav $B$ je třída obsahující počáteční stav $A$.
\item Množina přijímajících stavů $B$ jsou bloky odpovídající přijímajícím stavům $A$.


Podmnožinová konstrukce (FA z NFA)

\pojem{Podmnožinová konstrukce} začíná s NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Cílem je popis deterministického DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$, pro který $L(N)=L(D)$.
\begin{itemize}
\item $Q_D$ je množina podmnožin $Q_N$, $Q_D={\cal P}(Q_N)$ (potenční množina). {\footnotesize Nedosažitelné stavy můžeme vynechat.}
\item $F_D=\{S: S\in {\cal P}(Q_N)\ \&\ S \cup F_N \neq \emptyset\}$, tedy $S$ obsahuje alespoň jeden přijímající stav $N$.
\item Pro každé $S\subseteq Q_N$ a každý vstupní symbol $a\in \Sigma$,
$\delta_D(S,a)=\bigcup_{p \in S}\delta_N(p,a)\hbox{.}$
\end{itemize}



Page:  1  2  3  4  (Next)
  ALL