\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}

\newcommand{\ra}{\ensuremath{\rightarrow}}

\setlength{\textheight}{26cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-1cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\centerline{\bf{Formális nyelvek pótzárthelyi}}
\centerline{2001. április 17.}
\vspace*{1cm}
\noindent
\\
\ \
\\
1. Adj minimálautomatát a 
tizes számrendszerben felírt, 3-mal osztható természetes 
számokat tartalmazó nyelvre! 
Egy természetes szám nem kezdődhet nullával, kivéve ha
ő maga a 0 szám.
\\
\ \ \\
2. Adj meg egy egyirányban mozgó, egy kezdőállapottal rendelkező, 
determinisztikus véges automatát, mely egyenértékű az alábbi kétirányban mozgó 
véges automatával (vagyis ugyanazt a nyelvet fogadja el)! 
\begin{tabbing}
\hspace*{2cm} \=$\delta(S,a)=(A,h)$\hspace*{2cm}\=$\delta(S,b)=(B,e)$\\
\>$\delta(A,a)=(A,h)$\>$\delta(A,b)=(B,e)$\\
\>$\delta(B,a)=(S,e)$\>$\delta(B,b)=(A,e)$
\end{tabbing}
Kezdőállapot az $S$, elfogadó állapot az $A$, $e$ jelentése: előre, 
$h$ jelentése: hátra. 
\\
\ \ 
\\
3. Add meg reguláris kifejezéssel az alábbi nyelvtan által 
generált nyelv {\underline {komplementerét}}! 
\begin{tabbing} 
\hspace*{2cm}\=$S\ra aS$\=$\;|\;bA\;|\;bB\;|\;b$\\ 
\>$A\ra aA$\>$\;|\;aS\;|\;bS\;|\;a$\\ 
\>$B\ra aA$\>$\;|\;bB\;|\;\epsilon$ 
\end{tabbing}   
4. Adj egy darab kezdőállapottal rendelkező, determinisztikus 
véges automatát és
reguláris kifejezést az alábbi nyelvhez:\\
$L=\{\;w\in {\{\;0,1\;\}}^*\;|\; w$-ben páros sok 1-es van, 
és $w$-ben nem fordul elő részszóként a $010\;\}$
\\  
\ \ 
\\
5. Döntsd el, hogy reguláris-e a következő nyelv!
\vspace*{.2cm}\\
$L=\{\;a^{2^n}\;|\; n\geq 0\;\}$\\
Azaz a nyelvben a 2-hatvány darab a-ból álló szavak vannak. \\
\ \ 
\\
{\bf Mindegyik feladat 6 pontot ér.
\\
Válaszaidat mindig indokold meg, magyarázat nélküli megoldásokat nem 
fogadunk el. \\
Jó munkát!}
 


\end{document}








%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
