Slovník pojmů (ve vývoji)



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

Page: (Previous)   1  2  3  4  (Next)
  ALL

Dvousměrné (dvoucestné) konečné automaty

\pojem{Dvousměrným (dvoucestným) konečným automatem} nazýváme pětici $A=(Q,\Sigma, \delta, q_0,F)$, kde
\begin{enumerate}[<+->]
 \item $Q$ je konečná množina stavů,
 \item $\Sigma$ je konečná množina vstupních symbolů
 \item  přechodové funkce $\delta$ je zobrazení z $Q \times \Sigma \rightarrow Q\times\{-1,0,1\}$ \alert{rozšířená o pohyb hlavy}
 \item $q_0\in Q$ počáteční stav
 \item a množina přijímajících stavů $F\subseteq Q$.
\end{enumerate}


Mooreův stroj

\pojem{Mooreovým (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \mu,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \mu) $, kde
\begin{itemize}
 \item[] $Q$ je konečná neprázdná množina stavů
 \item[] $\Sigma$ je konečná neprázdná množina symbolů (vstupní abeceda)
 \item[] $Y$ je konečná neprázdná množina symbolů (\pojem{výstupní abeceda})
 \item[] $\delta$ je zobrazení $Q\times \Sigma \rightarrow Q$ (přechodová funkce)
 \item[] $\mu$ je zobrazení $Q\rightarrow Y$ (\pojem{značkovací funkce})
 \item[] $q_0\in Q$ (počáteční stav)
\end{itemize}


Mealyho stroj

\pojem{Mealyho (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \lambda_M,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \lambda_M) $, kde
\begin{itemize}
 \item[] $Q$ je konečná neprázdná množina stavů
 \item[] $\Sigma$ je konečná neprázdná množina symbolů (vstupní abeceda)
 \item[] $Y$ je konečná neprázdná množina symbolů (výstupní abeceda)
 \item[] $\delta$ je zobrazení $Q\times \Sigma \rightarrow Q$ (přechodová funkce)
 \item[] $\lambda_M$ je zobrazení $Q\rightarrow Y$ (\pojem{výstupní funkce})
 \item[] $q_0\in Q$ (počáteční stav)
\end{itemize}


palindrom

\pojem{Palindrom} je řetězec $w$ stejný při čtení zepředu i zedadu, tj. $w=w^R$.

 

Jazyk palindromů není regulární, je bezkontextový.


Gramatika = Formální (generativní) gramatika

Formální (generativní) gramatika je $G=(V,T,P,S)$ složena z
\begin{itemize}
 \item konečné množiny \pojem{neterminálů} (variables) $V$
 \item neprázdné konečné množiny \pojem{terminálních symbolů} (\pojem{terminálů}) $T$
 %, např. $\{0,1\} $.
 \item \pojem{počáteční symbol} $S\in V$.
 \item konečné množiny  \pojem{pravidel} (\pojem{produkcí}) $P$ reprezentující rekurzivní definici jazyka. Každé pravidlo má tvar:
 \begin{itemize}
  \item $\alpha A \beta\rightarrow \omega$, $A\in V,\alpha,\beta,\omega\in (V\cup T)^*$
  \begin{itemize}
   \item[] tj. levá strana obsahuje aspoň jeden neterminální symbol.   
  \end{itemize}
   \end{itemize}
\end{itemize}


Derivace $\Rightarrow^*$

Mějme gramatiku $G=(V,T,P,S)$.
\begin{itemize}
 \item Říkáme, že $\omega$ se \pojem{přímo přepíše} na $\gamma$ (píšeme $\omega\Rightarrow_G \gamma$ nebo $\omega\Rightarrow \gamma$) jestliže
 
 \begin{itemize}
   \item[] $\exists \alpha,\beta,\eta,\nu \in (V\cup T): \omega=\eta\alpha\nu$, $\gamma=\eta\beta\nu$ a $(\alpha\rightarrow \beta)\in P$.
 \end{itemize}
\item Říkáme, že $\omega$ se \pojem{přepíše} na $\gamma$ (píšeme $\omega\Rightarrow^* \gamma$) jestliže
\begin{itemize}
 \item[] $\exists \alpha_1,\ldots,\alpha_n\in (V\cup T)^*: \omega=\alpha_1\Rightarrow\alpha_2\Rightarrow\ldots\Rightarrow\alpha_n=\gamma$,
 \item[] tj. také $\omega\Rightarrow^*\omega$.
\end{itemize}
\item Posloupnost $\alpha_1,\ldots,\alpha_n $ nazýváme \pojem{derivací (odvozením)}.
\item Pokud $\forall i\neq j: \alpha_i\neq \alpha_j$, hovoříme o \pojem{minimálním odvození}.
\end{itemize}


Derivační strom

Mějme gramatiku $G=(V,T,P,S)$. \pojem{Derivační strom} pro $G$ je strom, kde:
\begin{itemize}
 \item každý vnitřní uzel je ohodnocen neterminálem $V$.
 \item Každý uzel je ohodnocen prvkem $\in V \cup T \cup \{\epsilon\} $.
 \item Je--li uzel ohodnocen $\epsilon$, je jediným dítětem svého rodiče.
 \item Je--li $A$ ohodnocení vrcholu a jeho děti \alert{zleva pořadě} jsou ohodnoceny $X_1,\ldots,X_k$, pak $(A\rightarrow X_1,\ldots,X_k) \in P $ je pravidlo gramatiky.
\end{itemize}


Jazyk generovaný gramatikou $G$

\pojem{Jazyk $L(G)$} generovaný gramatikou $G=(V,T,P,S)$ je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu.


Sentenciální formy

Mějme CFG $G=(V,T,P,S)$. Libovolný řetězec $\alpha\in (V\cup T)^*$ který lze odvodit $S\Rightarrow^*\alpha$ nazýváme \pojem{sentenciální forma}.


Jednoznačnost a víceznačnost CFG

\item Bezkontextová gramatika  $G=(V,T,P,S)$ je \pojem{víceznačná} pokud existuje aspoň jeden řetězec $w\in T^*$ pro který můžeme najít dva různé derivační stromy, oba s kořenem $S$ dávající slovo $w$.

 \item V opačném případě nazáváme gramatiku \pojem{jednoznačnou}.

 \item Bezkontextový jazyk $L$ je \pojem{jednoznačný}, jestliže existuje jednoznačná CFG $G$ tak, že $L=L(G)$.

 \item \pojem{Bezkontextový jazyk $L$ je (podstatně) nejednoznačný}, jestliže každá CFG $G$ taková, že $L=L(G)$, je nejednoznačná. Takovému jazyku říkáme i \pojem{víceznačný}.



Page: (Previous)   1  2  3  4  (Next)
  ALL