\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 (4)}}
\\
\ \ 
\\
{\bf 2000. október  2., hétfő}
\\
\ \ 
\\
1.
Adjunk reguláris kifejezést az alábbi automatához!
\\
\ \ \\
\includegraphics{r8.eps}
\\
\ \ 
\\
2. Add meg reguláris kifejezéssel az 
alábbi automata által elfogadott nyelv
{\em komplementerét}! 
($\Sigma = \{a,b\}$)\\
\\
\ \ \\
\includegraphics{minta.eps}\\
\ \ \\
3. 
Adj meg egy olyan (nemdeterminisztikus) véges automatát, amelynek nyelve 
az $(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le.
\\
\ \ \\
4. 
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 $$
\ \ \\
5. Legyen $\Sigma=\{a,b,c\}$, továbbá
$L_1 = \{w: |w|_a \mbox{ páratlan és } |w|_b \mbox{ páros}\}$ és
$L_2$ álljon azokból az $a$-val kezdődő, $c$-vel 
végződő szavakból, amelyekben a három karakter ciklikusan követi egymást (azaz
$a$ nem állhat közvetlenül $b$ után, $b$ nem állhat közvetlenül $c$ után és 
$c$ nem állhat közvetlenül $a$ után).
Szerkesszen az $L_1 \cap L_2$  nyelvre minimálautomatát!
\\
\ \ \\
6. 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\cap L^2$, $L^*$! 
Az első és az utolsó nyelvet adja meg reguláris kifejezéssel 
is! ($\Sigma = \{a,b\}$) 
\\
 \ \ \\
7. Reguláris-e az $\{\; a^mb^n\;|\; m\leq n\leq 2m\;\}$ nyelv?
\\
\ \ \\
8. Reguláris-e az 
$ \{a^ib^j\;|\; i>j\}$ nyelv?
\\
\ \ \\
\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: 
