\documentclass[12pt]{article}

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


\setlength{\textheight}{25cm}

\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 (3)}}
\\
\ \ \\
{\bf 2005. szeptember 29., csütörtök}
\\
\ \ 
\\
1. Adjuk meg az alábbi automatához tartozó minimálautomatát!
\\
\ \ \\
\includegraphics{r9.eps}
\\
\ \ 
\\
2. 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}
\ \ \\ \ \ \\ 
\ \ \\
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. Készítsünk minimálautomatát az alábbi nyelvhez ($\Sigma=\{a,b\}$):
\\
$L =\{ w : |w|_a  \mbox{ páros}, 
                  |w|_b  \mbox{ páros és }
                  |w| \mbox{ osztható 4-gyel}\}$
\\
\ \ 
\\
6. 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!
(Ha a szóban kevesebb, mint három betű van, akkor az elfogadandó.)
\\ \ \ \\
7. Legyen $\Sigma=\{a,b\}$ és az $L$ nyelvbe tartozzanak azok 
a szavak, melyekben  -ha van egyáltalán- 
a teljes homogén a-sorozatok hossza páratlan.
\\
Szerkesszen az alábbi nyelvekre minimálautomatát: $L$, $L^2$,
$L\cap L^2$, $L^*$.
\\ 
\ \ 
\\
\newpage
\noindent
8.  Legyen $L_1$ és $L_2$ az alábbi két nyelv:
\\
$L_1$ azokat a  
$\Sigma$ feletti szavakat tartalmazza, amelyekben
${|w|}_a$ és ${|w|}_b$ is páratlan.
Az $L_2$ azon szavakból áll, ahol ${|w|}_a$ és ${|w|}_b$ is páros.
\\
(i) Adjon minimálautomatát ${L_1}^2$-re és $L_2$-re!
\\
(ii) Döntse el, hogy ${L_1}^2$ egyenlő-e $L_2$-vel!
\\
(iii)
Ha nem azonosak, akkor adjon minimálautomatát a két nyelv 
szimmetrikus differenciájára!
\\
\ \ 
\\
9. Az $L$ nyelv azon ${\{a,b\}}^*$ feletti szavakból áll, 
melyekben  páratlan sok teljes homogén b-sorozat van.
\\
Készítsen minimálautomatát az $L^2\cap L$ nyelvre!
\\ \ \ \\
10. Az $L$ nyelvbe tartozzanak azok 
a szavak, melyekben  van páratlan teljes homogén részsorozat.
Szerkesszen minimálautomatát az alábbi nyelvekre:
$L$, $L^2$, $L\cap L^2$, $L^*$!
\\ \ \ \\
11. Legyen $L_1$ azon $\{a,b\}$ feletti szavak nyelve, mely szavakban 
páros sok $a$ van, $L_2$ pedig azon $\{a,b\}$ feletti szavak nyelve, 
mely szavakban páratlan sok $b$ van. \\
Adj minimálautomatát az $L_1$, $L_2$, $L_1\cup L_2$, $L_1\cap L_2$, ${L_1}^*$, 
${L_2}^*$, $L_1L_2$ és $\overline{L_1}$ nyelvekre!
\\ \ \ \\
12. Az $L$ nyelvből képezzük azt a min(L)-lel jelölt nyelvet, ami azon
szavakat tartalmazza, melyeknek egyetlen valódi kezdőszelete sincs
$L$-ben. Bizonyítsd be, hogy ha $L$ reguláris, akkor min(L) is az.


\end{document}

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




