\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}{-2.5cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\noindent
{\large{\bf Formális nyelvek gyakorlat (5)}}
\\
\ \ 
\\
{\bf 2001. március 13., kedd}
\\
\ \ 
\\
1. Az alábbi kétirányú véges automatához kellene minimálautomatát
adni:
\begin{tabbing}
$\delta(A,a)=(A,e)$ \ \ \ \  \= $\delta(A,b)=(B,e)$ \\
$\delta(B,a)=(A,e)$ \ \ \ \  \> $\delta(B,b)=(B,h)$ 
\end{tabbing}
Kezdőállapot az $A$, elfogadó állapotok az $A$ és a $B$. 
\\
\ \ \\
2.   Legyen egy kétirányú mozgást végző automata szabályrendszere 
a következő:
\begin{tabbing}
$\delta(S,a)=(P,e)$ \ \ \ \  \= $\delta(S,b)=(Q,e)$ \\
$\delta(P,a)=(P,e)$ \ \ \ \  \> $\delta(P,b)=(Q,e)$ \\
$\delta(Q,a)=(S,h)$ \ \ \ \  \> $\delta(Q,b)=(S,e)$
\end{tabbing}
Kezdőállapot az S, elfogadó állapotok az S és a P.
Készítsen minimálautomatát a fenti automata által elfogadott nyelvre!
\\
\ \ \\
3. Adott az alábbi kétirányban mozgó véges automata:
\begin{tabbing}
$\delta(S,a)=(P,e)$\hspace*{1.5cm}\=$\delta(S,b)=(Q,e)$
\hspace*{1.5cm}\=$\delta(R,a)=(V,h)$\hspace*{1.5cm}\=$\delta(R,b)=(V,h)$\\
$\delta(P,a)=(R,e)$\>$\delta(P,b)=(Q,e)$\> 
$\delta(T,a)=(V,h)$\>$\delta(T,b)=(V,h)$\\
$\delta(Q,a)=(S,h)$\>$\delta(Q,b)=(T,e)$\>
$\delta(V,a)=(S,e)$\>$\delta(V,b)=(S,e)$
\end{tabbing}
Valamennyi állapot elfogadó állapot.
Készítsen az automata által elfogadott nyelvre minimálautomatát! 
\\
\ \ \\
4. {\bf HF, írásban} Milyen nyelvet fogad el az alábbi kétirányú véges automata?
\begin{center}
\begin{tabular}{lcp{3cm}lcl}
$\delta(q_0,a)$ &=& $(q_0,e)$ & $\delta(q_0,b)$ &=& $(q_1,h)$ \\
$\delta(q_1,a)$ &=& $(q_2,e)$ & $\delta(q_1,b)$ &=& $(q_3,h)$ \\
$\delta(q_2,a)$ &=& $(q_3,h)$ & $\delta(q_2,b)$ &=& $(q_0,e)$ \\
$\delta(q_3,a)$ &=& $(q_3,h)$ & $\delta(q_3,b)$ &=& $(q_3,h)$ 
\end{tabular}
\end{center}
Elfogadó állapot a $q_0$.
\\ \ \ \\
5. Tekintsük az alábbi két nyelvet:
$L=\{A,B,\ldots, Z, a,b, \ldots, z\}$ és $D=\{0,1,2,\ldots, 9\}$.
\\
Fogalmazd meg szavakkal, hogy mely szavakból állnak az alábbi nyelvek:
\\
$L\cup D$, $LD$, $L^4$, $L^*$, $L{(L\cup D)}^*$, $D^+$.
\\
\ \ \\
6. Fogalmazd meg szavakkal, hogy mik az alábbi reguláris kifejezések által 
leírt nyelvek:\\
$0{(0+1)}^*0$, ${(0+1)}^*0{(0+1)}{(0+1)}$, $0^*10^*10^*10^*$, 
${(a+b)}^*(aa+bb){(a+b)}^*$, ${(a^*+b^*)}^*$
\\
\ \ \\
7. Add meg reguláris kifejezéssel az alábbi $\Sigma=\{a,b\}$ feletti nyelveket:\\
(a) $\{w\in  {\Sigma}^*\;|\;$ w-ben van legalább két a$\}$
\\
(b) $\{w\in  {\Sigma}^*\;|\; $ w-ben minden teljes homogén a-részsorozat páros és
minden teljes homogén b-részsorozat páros $\}$    
\\
(c) $\{w\in  {\Sigma}^*\;|\; $ van olyan betű amiből $\geq 2$ van w-ben$\}$
\\
(d) $\{w\in  {\Sigma}^*\;|\; $ w-ben minden teljes homogén a-részsorozat páros
és minden teljes homogén b-részsorozat páratlan $\}$    
\\
\ \ \\
\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: 

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