\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 (2)}}
\\
\ \ 
\\
{\bf 2001. február 20., kedd}
\\
\ \ 
\\
1. Nézzük a következő véges automatát, melynek input ábécéje $\{a,b\}$:
\vspace*{.3cm}
\\
\includegraphics{gy2.eps}
\vspace*{.3cm}
\\
(a) Mi történik az automatában az $aaa$, $ab$ és $abb$ szavak hatására?\\
(b) Mi az automata által elfogadott nyelv?
\\
(c)
Alakítsd át az automatát teljesen specifikált automatává (minden állapotban
legyen minden karakterre legalább egy kivezető  nyíl)\\
(d) Alakítsd át úgy az automatát, hogy csak egy végállapota legyen és ebből 
az egy végállapotból ne vezessen nyíl sehova\\
\\
Természetesen a (c) és (d)-beli átalakításkor az elfogadott nyelv 
nem változhat.
\\
\ \ 
\\
2. Hogyan kell általában úgy átalakítani egy véges automatát, hogy az új
automata\\
(a) teljesen specifikált legyen?
\\
(b) csak egy végállapotot tartalmazzon és abból ne vezessen sehova se nyíl?  
\\ \ \ \\
3. Mutasd meg, hogy egy  ``elfuserált'' véges automatát, aminek több
kezdőállapota van, mindig át lehet alakítani egy olyanná, aminek csak egy van és 
abba se vezet be nyíl. 
\\
\ \ 
\\
3. Adjunk (lehetőleg determinisztikus) véges automatát az alábbi nyelvhez: \\
$L=\{w\in {\{a,b\}}^*\;|\;{|w|}_a $ osztható hárommal, ${|w|}_b$
osztható kettővel$\}$.
\\
\ \ \\
4. Adjunk (lehetőleg determinisztikus) véges automatát ahhoz az $\{a,b\}$ 
feletti nyelvhez, melybe azon szavak tartoznak, amelyekben
minden teljes homogén  $a$-sorozat hossza osztható 3-mal és minden teljes homogén b-sorozat hossza osztható 2-vel.
\\
\ \ \\
5. Adjunk véges automatát \\
(a) az üres nyelvre, azaz $L=\emptyset$,
\\
(b) a csak az $\epsilon$-t tartalmazó nyelvre, azaz $L=\{\epsilon\}$.
\\
\ \ 
\\
6. Legyen $\Sigma=\{a,b,c\}$. A nyelv szavaira a következő két dolog igaz: 
\\
$(i)$ összesen páratlan sok karakter van bennük\\
$(ii)$ $a$ után közvetlenül nem jöhet $c$, $b$ után $a$, $c$ után $b$.
\\
Véges (lehetőleg determinisztikus) automata kell erre a nyelvre.\\
\ \ 
\\
7. Legyen $\Sigma=\{0,1\}$. A jelsorozatokat tekintsük mint bináris számokat.
Adjunk automatát, amely pont a hárommal osztható számokat fogadja el!
Vegyük figyelembe, hogy szám 0-val nem kezdődik, kivéve ha az maga a 0.
\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: 
