\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}

\newcommand{\ra}{\ensuremath{\rightarrow}}


\setlength{\textheight}{26cm}

\setlength{\textwidth}{15cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-3cm}

\setlength{\oddsidemargin}{0.4cm}
\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\noindent
{\centerline {\large \bf{ Formális nyelvek vizsga}}
\vspace*{.1cm} \\ 
{\centerline {\large \bf{2001. június 12.}}}
\vspace*{.5cm}\\
\hrule
\ \ \vspace*{.1cm}\\
{\it A feladatok nem nehézségi sorrendben vannak. Az első 5 példa 8-8 
pontot ér, az utolsó példa (a) része 6 pont, a (b) és (c) rész pedig 
2-2 pont. Így összesen 50 pontot lehet elérni, a vizsga 
20 ponttól sikeres. \\
A MEGOLDÁSOKAT INDOKOLD MEG! \\
Jó munkát!} 
\vspace*{.1cm}\\
\hrule
\vspace*{.3cm}
\begin{enumerate}

\item Adj {\underline {minimálautomatát}} 
az alábbi véges automata által elfogadott nyelvhez!
\vspace*{.3cm}\\
\includegraphics{v2.eps}


\item Adott 37 reguláris nyelv az $\{a,b\}$ ábécé felett.
\\
{\underline {Igaz-e}}, hogy az alábbi nyelv mindenképp reguláris?
$$ L=\{w\in {\{a,b\}}^*\;|\; w \;\;a \;\;nyelvek \;\;
t\ddot obbs\acute eg\acute eben \;\;(teh\acute at \;\;legal\acute abb 
\;\;19 \;\;nyelvben)
\;\;benne \;\;van\}$$

\item Adj {\underline {minél egyszerűbb osztályú nyelvtant} }
az alábbi nyelvhez!
$$L=\{a^nb^{2m}a^{n}\;|\;n,m\geq 1\}$$
A feladat része annak megmutatása is, 
hogy egyszerűbb nyelvtannal a nyelv nem generálható!

\item Adj {\underline {jellemző nyelvtant}} az alábbi fordításhoz:
$$ \mathcal{T}=\{(w,ww^{-1})\;|\;w\in {\{a,b\}}^*\}$$
Ha $w=x_1\ldots x_n$, akkor $w^{-1}=x_n\ldots x_1$, azaz $w^{-1}$ a 
$w$ szó tükrözésével, visszafele való leírásával kapható. 
A fordítást tehát olyan szópárok alkotják, melyek második tagja úgy áll elő. hogy
az első tag után írjuk az első tag tükörképét.

 
\item Adj az alábbi nyelvtannal ekvivalens (ugyanazt a nyelvet generáló) 
\\
{\underline {jólfésült, Chomsky normál alakú}} nyelvtant:
\vspace*{.2cm}\\
$S\ra A\;|\;C$,  $A\ra aB\;|\;bS\;|\;b$, 
$B\ra AB\;|\;Ba$,
$C\ra AS\;|\;b$ 


\item (a) Készíts {\underline {gyenge $LL(k)$ elemzőt}} minél kisebb $k$-val 
az $S\ra AB$, $A\ra aAb\;|\;\epsilon$, $B\ra bBc\;|\;\epsilon$  
nyelvtanhoz!
\vspace*{.1cm}\\
(b) Lehet-e erős $LL(k)$ elemzőt csinálni a fenti nyelvtanhoz, 
az (a) pontban kapott $k$ értékkel?
\\
(c) Elemezd az (a) pontban kapott elemzővel az $abbc$ szót!

\end{enumerate}
\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: 
