\documentclass[12pt]{article}

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


\setlength{\textheight}{26cm}

%\setlength{\textwidth}{16cm}

%\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-1cm}

%\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. május 29.}}}
\vspace*{1cm}\\
\hrule
\ \ \vspace*{.5cm}\\
{\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 8 pont, a (b) része pedig 
2. Így összesen 50 pontot lehet elérni, a vizsga 
20 ponttól sikeres. \\
A MEGOLDÁSOKAT INDOKOLD MEG! \\
Jó munkát!} 
\vspace*{.4cm}\\
\hrule
\vspace*{1cm}
\begin{enumerate}
\item Adj {\underline {minimálautomatát}} ahhoz a nyelvhez, mely azon 
$\{a,b\}$ ábécé feletti szavakból áll, melyek legalább kétszer 
tartalmazzák a $bab$ részszót! Vigyázat: a két előfordulás lehet átfedő, 
tehát például a $babab$ szó is ilyen!
A minimalitást is indokolni kell és az automata jóságát is!

\item Bizonyítsd be, hogy {\underline {nem reguláris}} az a nyelv, 
mely azon $2n$, $n\geq 0$ (tehát páros) hosszúságú  
$\{a,b\}$ feletti szavakból áll, melyeknek 
mind az első $n$, mind a második $n$ karaktere között páros sok 
$a$ szerepel. Tehát jó szavak például: $bbaa$, $baaaba$, $bb$, $\epsilon$, 
rosszak például: $abb$, $aaba$.   


\item Adj {\underline {veremautomatát}} az előző feladatban leírt nyelvre!
Jelöld, hogy az automata hogyan fogad el és lásd el magyarázatokkal
az automata szabályait (melyik mit csinál és miért)! 

\item Adj az alábbi nyelvtannal ekvivalens (ugyanazt a nyelvet generáló) 
{\underline {Greibach normál alakú nyelvtant}}:
\\
\vspace*{.2cm}\\
{\centerline {$S\ra BS\;|\;a$ \\ $B\ra SS\;|\;b$}}

\item Készíthető-e   {\underline {gyenge $LL(1)$}}
elemző az alábbi nyelvtanhoz?\\
\vspace*{.2cm}\\
{\centerline {$S\ra ABBA$ \\ $A\ra a\;|\;\epsilon$\\ $B\ra b\;|\;\epsilon$}}
\\

\item (a) Készíts {\underline {$LR(1)$ elemzőt}} az $S\ra aSS\;|\;b$ 
nyelvtanhoz!
\vspace*{.1cm}\\
\\
(b) Elemezd az (a) pontban kapott elemzővel az $ababb$ 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: 
