\documentclass[11pt]{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 (2)}}
\\
\ \ \\
{\bf 2005. szeptember 22., csütörtök}
\\
\ \ 
\\
1. Adjunk determinisztikus véges automatát az alábbi nyelvhez: \\
$L=\{w\in {\{a,b\}}^*\;|\;{|w|}_a $ osztható hárommal, ${|w|}_b$
osztható kettővel$\}$.
\\
\ \ \\
2. Legyen $\Sigma=\{a,b,c\}$. A nyelv szavaira a következő két dolog igaz: 
\\
$\bullet$ összesen páratlan sok karakter van bennük\\
$\bullet$ $a$ után közvetlenül nem jöhet $c$, $b$ után $a$, $c$ után $b$.
\\
Determinisztikus véges automata kell erre a nyelvre.
\\
\ \ 
\\
3. Tegyük determinisztikussá az alábbi automatát!!
\\
\includegraphics{r4.eps}
\\
\ \ \\
4. Adjunk (jobb- és bal-)reguláris nyelvtant a 3. feladat automatájához!
\\
\ \ \\
5. 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.
\\ \ \ \\
6. 
Determinizálni kell ezt:
\\
\ \ 
\\
\includegraphics{r3.eps}
\\
\ \ 
\\
7. Készíts olyan véges automatát, amely a tizedestört alakban felírt
racionális számokat fogadja el.
Pontosabban az elfogadandó szám vagy tizedespont nélküli egész szám
(pl. {\bf 123}), vagy tartalmaz tizedespontot. Az utóbbi esetben azt is el kell
fogadni, ha az egészrész vagy a törtrész hiányzik, de persze legfeljebb az 
egyik hiányozhat (pl. helyes  az {\bf 123.456} vagy az {\bf 123.} vagy  a 
{\bf .456} is, de nem fogadható el ha a bemenet csak egyetlen pontból áll.).
Megköveteljük továbbá azt is, hogy az egészrész ne kezdődjön felesleges 0-kal
(de pl. a  {\bf 0.456} helyes).
\\ \ \ \\
8. Adjunk véges automatát \\
(a) az üres nyelvre, azaz $L=\emptyset$,
\\
(b) a csak az $\epsilon$-t tartalmazó nyelvre, azaz $L=\{\epsilon\}$.
\\
\ \ 
\\
\newpage
\noindent
9. Adjunk determinisztikus véges automatát a következő nyelvre:
\\
$L=\{w\in {\{0,1\}}^*\;|\;$ létezik két $0$ $w$-ben, melyek között 
néggyel osztható számú egyes áll$\}$.
\\
\ \ 
\\
10. Determinisztikus véges automata kéretik: \\
$L=\{w\in {\{a,b\}}^*\;|\;$ $w$-ben jobbról a 3. betű b$\}$ 
\\
\ \ 
\\
11. Készítsünk véges automatát, ami 
ugyanazt a nyelvet fogadja el, mint amit az alábbi jobb\-re\-guláris 
nyelvtan generál:\\
$S\ra aS\;|\;bB\;|\;b$\\
$A \ra aA\;|\;a\;|\;bC$\\
$B \ra bB\; |\; b\; |\; aA\; |\; a$\\
$C \ra bC\; |\; aS$ 
\\
\ \ \\
12. Készítsünk véges automatát, ami 
ugyanazt a nyelvet fogadja el, mint amit az alábbi balreguláris 
nyelvtan generál:\\
$S \ra Sb\; |\; Aa\; |\; a$\\
$A \ra Sa \;| \;Bb$\\
$B \ra Ba \;|\; Bb \;| \;\epsilon$ 
\\ \ \ \\
13. {\bf A 2. része nehéz}
\\
(a)
Adjunk $n+1$ állapotú nem determinisztikus VA-t az 
${(a+b)}^*a{(a+b)}^{n-1}$ nyelvhez!
\\
(b) Mutassuk meg, hogy minden DVA, ami elfogadja ezt a nyelvet
legalább $2^n$ állapotú!


\end{document}

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




