\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}
\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 Formális nyelvek gyakorlat (4)}}
\\
\ \ 
\\
{\bf 2001. március 6., kedd}
\\
\ \ 
\\
1. Az alábbi táblázattal adott egy véges automata, melynek 12 állapota van és
input ábécéje az $\{a,b\}$ halmaz. Kezdőállapot a $0$, 
elfogadó állapotok a $0$ és a $8$.\\
Minimalizáld az automatát!
\\
\ \ \\
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
&0&1&2&3&4&5&6&7&8&9&10&11 \\ \hline
a&3&9&11&2&11&6&8&10&1&4&8&4 \\ \hline
b&5&4&8&11&4&11&4&4&7&0&4&11 \\ \hline 
\end{tabular}
\ \ 
\\
\ \ \\
\ \ \\
2. Készítsünk minimálautomatát az alábbi nyelvhez:
\\
$L =\{ w : |w|_a  \mbox{ páros}, 
                  |w|_b  \mbox{ páros és }
                  |w| \mbox{ osztható 4-gyel}\}$
\\
\ \ 
\\
3. Álljon az $L$ nyelv $\{a,b\}^*$ azon szavaiból, melyek
ha $a$-ra végződnek, akkor nen tartalmaznak  $bb$ részszót, és
ha $b$-re végződnek, akkor nem tartalmaznak  $aa$ részszót.
Készíts minimálautomatát ehhez a nyelvhez!
\\ \ \ \\
4. Adjunk minimálautomatát az alábbi nyelvtan
által generált nyelvhez
\begin{eqnarray*}
S &\ra& A \mid ab, \\
A &\ra& B \mid bA, \\
B &\ra& bB \mid C \mid a, \\
C &\ra& bb
\end{eqnarray*}\ \  
\\
\ \ 
\\
5. Legyen $\Sigma=\{a,b\}$ és álljon az  $L$ nyelv azokból 
a legalább 3 hosszúságú szavakból, melyekben minden három 
hosszú részszó legalább 2 darab $a$ betűt tartalmaz.
Készíts minimálautomatát az $L$ nyelvhez!
\\
\ \ \\
6. Az $L$ nyelv szavaiban a szavak nem ugyanazzal a betűvel kezdődnek, 
mint amivel végződnek, így páros számú homogén 
részsorozat van minden szóban.
Párosítva ezeket (az elsőt a másodikkal, a harmadikat a negyedikkel, 
stb.), minden pár hossza páratlan, tehát a pár 
egyik tagja páros a másik meg páratlan. Adjunk az $L$ nyelvhez 
minimálautomatát! 
\\
\ \ \\
7. Az $L$ nyelv  mondatainak hossza osztható
hárommal, az üres szó nincs a nyelvben.
Ezek szerint a nyelv egy tetszőleges szavának 
karaktereit hármasával csoportokra oszthatjuk (az elejéről kezdve).
Minden csoportban valamelyik karakter legalább kétszer előfordul. 
A nyelvbe azon  szavak tartoznak, melyekben ez
a többségi karakter a szomszédos csoportokban egymástól különbözik.
Szerkesszen minimálautomatát a fenti  nyelvre! 

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

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