\documentclass[12pt]{article}

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


\setlength{\textheight}{26cm}

\setlength{\textwidth}{15cm}

%\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. június 19.}}}
\vspace*{1cm}\\
\hrule
\ \ \vspace*{.4cm}\\
{\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. Így összesen 50 pontot lehet elérni, a vizsga 
20 ponttól sikeres. \\
A MEGOLDÁSOKAT INDOKOLD MEG! \\
Jó munkát!} 
\vspace*{.2cm}\\
\hrule
\vspace*{.6cm}
\begin{enumerate}

\item Adj {\underline {minimálautomatát}} ahhoz a nyelvhez, mely azon 
$\{0,1\}$ ábécé feletti szavakból áll, melyekben 
minden páros hosszú teljes homogén 0-sorozatot páros hosszú teljes homogén 
1-sorozat követ és minden páratlan hosszú teljes homogén 0-sorozatot 
páratlan hosszú teljes homogén 
1-sorozat követ. 
A minimalitást is indokolni kell és az automata jóságát is!

\item Adj {\underline {reguláris nyelvtant}} az alábbi nyelvhez!
$$\{0^a1^b0^c\;|\;b=2, a+c \;\;p\acute aratlan\}$$
Magyarázd el, hogy a nyelvtanod hogyan működik és miért az adott 
nyelvet generálja!

\item Adj {\underline {veremautomatát}} ahhoz az 
\{a,b\} feletti nyelvhez, mely azon szavakból áll, melyek hossza 
páratlan  és legalább 3, s amelyekben az első betű 
megegyezik a középső betűvel és az utolsó betűvel is.  
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 SSa\;|\;b$ }}

\item Bizonyítsd be, hogy {\underline {nem elemezhető gyenge precedencia 
elemzővel}}
az alábbi nyelvtan!\\
\vspace*{.2cm}\\
{\centerline {$S\ra a\;|\;(S)\;|\;i(L)$,
 $L\ra L-S\;|\;S$}}


\item (a) Készíts {\underline {gyenge $LL(k)$ elemzőt}} minél kisebb $k$-val
az $S\ra aaSbb\;|\;a\;|\;\epsilon$ 
nyelvtanhoz!
\vspace*{.1cm}\\
(b) Van-e a (a) pontban kapott $k$-val erős $LL(k)$ elemző a nyelvtanhoz? 
\\
(b) Elemezd az (a) pontban kapott elemzővel az $aaaaabbb$ 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: 

%%% TeX-master: t
%%% End: 
