\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}
\newcommand{\ra}{\ensuremath{\rightarrow}}


\setlength{\textheight}{25cm}

\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 2005. október 20., csütörtök}
\\
\ \ 
1. Add meg reguláris kifejezéssel az alábbi véges automata által
elfogadott nyelvet!
\\ \ \ \\
\includegraphics{regkif.eps}
\\
\ \ \\
2. Adjunk reguláris kifejezést az alábbi automatához!
\\
\ \ \\
\includegraphics{r8.eps}
\\
\ \ 
\\
3. Add meg reguláris kifejezéssel az 
alábbi automata által elfogadott nyelv
{\em komplementerét}! 
($\Sigma = \{a,b\}$)\\
\\
\ \ \\
\includegraphics{minta.eps}\\
\ \ \\
4. 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!
\\
\ \ \\
5. 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}  
\ \ \\
\newpage
6. Adott az alábbi $CF$ nyelvtan:
\begin{eqnarray*}
S& \ra & 00S\;|\;RP\;|\;QT\\
P&\ra&00P\;|\;RS\;|\;TU\;|\;Q\\
Q  & \ra &00\;|\;RT  \\
R  & \ra &11  \\
T & \ra &\epsilon  
\end{eqnarray*}
(i) Adja meg a nyelvet reguláris kifejezésként!\\
(ii) Készítsen hozzá harmadosztályú nyelvtant!\\
(iii) Adja meg a nyelvet elfogadó minimálautomatát!
\\ \ \ \\
7. Reguláris-e az $\{\; a^mb^n\;|\; m\leq n\leq 2m\;\}$ nyelv?
\\
\ \ \\
8. Reguláris-e az 
$ \{a^ib^j\;|\; i>j\geq 1\}$ nyelv?
\\ \ \ \\
9. Reguláris-e a 
$\{0^i1^j \;|\; lnko(i,j)\not = 1\}$  nyelv?
\\ \ \ \\
10. Reguláris-e a 
$\{0^n1^m0^{n+m}| n, m\geq 1\}$ nyelv?
\\
\ \ \\
11. Küszöböljük ki az $\epsilon$-szabályokat az alábbi CF
nyelvtanból!
\\
$S\ra ACb\;|\;a$, $A\ra aCBb\;|\;\epsilon$, $B\ra\epsilon\;\;a$, $C\ra AB$ 
\\ \ \ \\
12. Küszöböljük ki az $\epsilon$-szabályokat!\\
$S\ra ABC$, $A\ra BB|\epsilon$, $B\ra CC|a $, $C\ra AA|b$
\\ \ \ \\
13. Küszöböljük ki a láncszabályokat!\\
$E\ra E+T|T$, $T\ra T*F|F$, $F\ra (E)|a$
\\ 
\ \ 
\\
14. Küszöböljük ki a láncszabályokat!\\
$S\ra A|B$, $A\ra B|D|0B|1$, $B\ra C$, $C\ra B|A0$, $D\ra C$
\end{document}

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




