Slovník pojmů (ve vývoji)



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

Page:  1  2  3  4  (Next)
  ALL

Regulární výrazy

\pojem{Regulární výrazy} $RV(\Sigma)$ nad konečnou neprázdnou abecedou $\Sigma=\{x_1,x_2,\ldots,x_n\}$ a jejich hodnota $L(\alpha)$ jsou definovány induktivně:
Základ:
\begin{enumerate}
 \item Konstanty $\lambda$ a $\emptyset$ jsou regulární výrazy s hodnotami $L(\lambda)=\{\lambda\}$ a $L(\emptyset)=\emptyset$ (někdy značeno $\left[\lambda\right]$, $\left[\emptyset\right]$).
 \item Je--li $a\in \Sigma$, je ${\bf a}$ regulární výraz s hodnotou $L({\bf a})=\{a\}$.
 \item řecká písmena z počátku abecedy $\alpha,\beta$ budeme používat jako proměnné reprezentující libovolný jazyk $\alpha\in RV(\Sigma)$.
\end{enumerate}

Indukce: Jsou--li $\alpha$ a $\beta$ regulární výrazy s hodnotami $L(\alpha)$ and $L(\beta)$, pak
\begin{enumerate}
 \item $\alpha+\beta$ je RE s hodnotou $L(\alpha+\beta)=L(\alpha)\cup L(\beta) $.
 \item $\alpha\beta$ je RE s hodnotou $L(\alpha\beta)=L(\alpha)L(\beta)$. (Tečce používané u řetězců se vyhýbáme, aby se nepletla s jiným významem v  UNIX grep příkazu.)
 \item uzávěr $\alpha^*$ je RE s hodnotou $L(\alpha^*)=(L(\alpha))^*$.
 \item $(\alpha)$ je RE se stejnou hodnotou jako  $\alpha$, i.e. $L((\alpha))=L(\alpha)$.
\end{enumerate}
Každý regulární výraz dostaneme indukcí výše, tj. třída $RE(\Sigma)$ je nejmenší třída uzavřená na uvedené operace.


FA

viz konečné automaty (finite automata)


Chomského hierarchie


Chomského normální tvar CFG

O bezkontextové gramatice $G=(V,T,P,S)$ bez zbytečných symbolů kde jsou všechna pravidla v jednom ze dvou tvarů
\begin{itemize}
 \item $A\rightarrow BC$, $A,B,C\in V$,
 \item $A\rightarrow a$, $A\in V$, $a\in T$,
\end{itemize}
říkáme, že je v  \pojem{Chomského normálním tvaru (ChNF)}.


Uzávěrové vlastnosti

jazyk regulární bezkontext.

deterministické

bezkontextové

sjednocení ANO ANO NE
průnik ANO NE NE
∪ s RL ANO ANO ANO
doplněk ANO NE ANO
homomorfismus ANO ANO NE
inverzní hom. ANO ANO ANO

Příklad nerekurzivního, rekurzivně spočetného jazyka

Problém zastavení TM (halting problem) je algoritmicky nerozhodnutelný.

Neexistuje algoritmus, který by pro daný kód TM a daný vstup rozhodl, zda se TM zastaví.


lineárně omezený automat (LBA)

\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$.


rekurzivně spočetný jazyk

Jazyk nazveme \pojem{rekurzivně spočetným}, pokud je přijímán nějakým Turingovým strojem $T$ (tj. $L=L(T)$).


Turingův stroj přijímá jazyk

Turingův stroj $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ \pojem{přijímá jazyk} $L(M)=\{w\in \Sigma^*: q_0w \vm^* \alpha p \beta, p\in F, \alpha,\beta \in \Gamma^*\} $, tj. množinu slov, po jejichž přečtení se dostane do koncového stavu. Pásku (u nás) nemusí uklízet.


Konfigurace Turingova stroje ID

\pojem{Konfigurace Turingova stroje} (Instantaneous Description ID) je řetězec $X_1X_2\ldots X_{i-1}qX_iX_{i+1}\ldots X_n$ kde
\begin{itemize}
 \item $q$ je stav Turingova stroje
 \item čtecí hlava je vlevo od  $i$--tého symbolu
 \item $X_1\ldots X_n$ je část pásky mezi nejlevějším a nejpravějším symbolem různým od prázdného ($B$). S výjimkou v případě, že je hlava na kraji -- pak na tom kraji vkládáme jeden $B$ navíc.
\end{itemize}



Page:  1  2  3  4  (Next)
  ALL