\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 (6)}}
\\
\ \ 
\\
{\bf 2001. március 20., kedd}
\\
\ \ 
\\
1.
Adj meg egy olyan véges automatát, melyben nincs 
 $\epsilon$-átmenet és amelynek nyelve 
az $(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le.
\\
\ \ \\
2. 
Add meg reguláris kifejezéssel az 
alábbi automata által elfogadott nyelv
{\em komplementerét}! 
($\Sigma = \{a,b\}$)\\
\\
\ \ \\
\includegraphics{minta.eps}\\
\ \ \\
3. Legyen $L_1$ azon $\{a,b\}$ feletti szavak nyelve, mely szavakban 
páros sok $a$ van, $L_2$ pedig azon $\{a,b\}$ feletti szavak nyelve, 
mely szavakban páratlan sok $b$ van. \\
(a) Adj minimálautomatát az $L_1$, $L_2$, $L_\cup L_2$, $L_1\cap L_2$, ${L_1}^*$, 
${L_2}^*$, $L_1L_2$ és $\overline{L_1}$ nyelvekre!
(b) Adj reguláris kifejezést $L_1$-re és $L_2$-re!
\\
\ \ \\
4. Reguláris-e az $\{\; a^mb^n\;|\; m\leq n\leq 2m\;\}$ nyelv?
\\
\ \ \\
5. Döntsük el, hogy az alábbi két reguláris kifejezés által leírt
nyelv azonos-e!
$$ ((a+b) b^* a)^*  \quad \quad \mbox{\rm és} \quad \quad 
(a+b) (b+a(a+b))^* a + \epsilon $$
\\
\ \ \\
6. Adott az alábbi három reguláris nyelv:
\\
${(b^*ab^*a)}^*b^*$\hspace*{1cm}$a^*b{(a^*ba^*b)}^*a^*$\hspace*{1cm}
${(a+b)}^*a$\\
Legyen az $L$ nyelv azon szavak halmaza, amelyek a fenti három nyelv 
közül legalább kettônek mondatai!
\\
Adja meg az $L$-t elfogadó minimálautomatát!
\\
\ \ \\
7. Adott két nyelv az alábbi  két egyenletrendszerrel.
Készítse el a két nyelv metszetét felismerő minimálautomatát!
\begin{tabbing}
$S_1=aS_1+b(A+\epsilon)$\hspace*{3cm}\=$S_2=aS_2+b(B+\epsilon)$\\
$A=bS_1+a(A+\epsilon)$\>$B=aS_2+b(B+\epsilon)$
\end{tabbing}  
\ \ \\
8. 
Az $L$ nyelvbe tartozzanak azok 
a szavak, melyekben  van páratlan teljes homogén részsorozat.
Szerkesszen minimálautomatát az alábbi nyelvekre:
$L$, $L^2$, $L^*$! 
Az első és az utolsó nyelvet adja meg reguláris kifejezéssel 
is! ($\Sigma = \{a,b\}$) 


\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: 

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