\documentclass[10pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\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 Gyakorló feladatok formális nyelvekből}}
\\
\ \ 
\\
{\bf 4. gyakorlat}
\\
\ \ 
\\
1.
Ehhez a nyelvtanhoz kell reguláris kifejezés!
\\
$S\ra 1A|0B$, $A\ra 0A|1A|1$, $B\ra 0B|1B|0$. 
\\
\ \ \\
2. Add meg reguláris kifejezéssel azt a nyelvet amelyik a $\{0,1\}^*$
azon szavaiból áll, amikben nem fordul elő az 110 részszó!
\\
\ \ \\
3. 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!
\\
\ \ \\
4. 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=S_2+b(B+\epsilon)$
\end{tabbing}  
\ \ \\
5. Adjunk determinisztikus véges automatát az alábbi nyelvhez:
\\
$L=\{{(1111)}^+w\;|\;w\in{\{a,b\}}^*\}$
\\
\ \ \\
6. 
Legyen $\Sigma=\{a,b,c\}$ és 
$L = \{w: |w|_a + |w|_b \mbox{ páros és } 
          |w|_b + |w|_c \mbox{ páratlan} \}$.
Készítsünk minimálautomatát $L$-re, $L^2$-re és $L^*$-ra!
\\
\ \ \\
7. Az $L$ nyelv azon ${\{a,b\}}^*$ feletti szavakból áll, 
melyekben  páratlan sok teljes homogén b-sorozat van.
\\
(i) Készítsen minimálautomatát az $L^2\cap L$ nyelvre!
\\
(ii) Adja meg a metszet nyelvet reguláris kifejezéssel!
\\ \ \ \\
8. Reguláris-e a 
$\{0^n1^m0^{n+m}| n, m\geq 1\}$ nyelv?
\\
\ \ \\
9. Igazoljuk, hogy az 
$\{0^{n!}\;|\; n\geq 0\}$ nyelv nem reguláris!
\\ \ \ \\
10. Az $L$ nyelv ábécéje a $\{0,1\}$. A 
nyelvbe azok a szavak tartoznak, melyekben ${|w|}_0={|w|}_1$ 
és amelyek minden prefixében  $|{|w|}_0-{|w|}_1|\leq 1$.
\\
(i)
Írjuk le reguláris kifejezéssel a fenti nyelvet!
\\
(ii)
Adjunk a nyelvhez determinisztikus véges automatát! 
\\
\ \ \\
11.
 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!\\ 
\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: 

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