\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 (4)}}
\\
\ \ \\
{\bf 2005. október 13., csütörtök}
\\
\ \ 
\\
1. Fogalmazd meg szavakkal, hogy mik az alábbi reguláris kifejezések által 
leírt nyelvek és adj a reguláris kifejezésekhez determinisztikus véges
automatát!:\\
$0{(0+1)}^*0$,\\
 ${(0+1)}^*0{(0+1)}{(0+1)}$,\\
 $0^*10^*10^*10^*$, 
\\
${(a+b)}^*(aa+bb){(a+b)}^*$, \\
${(a^*+b^*)}^*$
\\
\ \ \\
2. Add meg reguláris kifejezéssel az alábbi $\Sigma=\{a,b\}$ feletti
nyelveket és adj hozzájuk determinisztikus véges automatát:\\
(a) $\{w\in  {\Sigma}^*\;|\;$ w-ben van legalább két a$\}$
\\
(b) $\{w\in  {\Sigma}^*\;|\; $ w-ben minden teljes homogén a-részsorozat páros és
minden teljes homogén b-részsorozat páros $\}$    
\\
(c) $\{w\in  {\Sigma}^*\;|\; $ van olyan betű amiből $\geq 2$ van w-ben$\}$
\\
(d) $\{w\in  {\Sigma}^*\;|\; $ w-ben minden teljes homogén a-részsorozat páros
és minden teljes homogén b-részsorozat páratlan $\}$    
\\
\ \ \\
3. 
Adj meg egy olyan determinisztikus véges automatát, amelynek nyelve 
az \\
$(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le.
\\
\ \ \\
4. 
Döntsük el, hogy az alábbi két reguláris kifejezés által leírt
nyelv azonos-e!
$$ ((a+b) b^* a)^*  \quad \quad \mbox{\rm és} \quad \quad 
(a+b) (b+a(a+b))^* a + \epsilon $$
\ \ \\
5. Adjunk determinisztikus véges automatát a $10+(0+11)0^*1 $ reguláris 
kifejezéshez!\\
\ \ 
\\
6. Mely szavakból áll  az a nyelv, amelyet az alábbi reguláris kifejezés ír le: \\
${(a+b)}^*[aa{(a+b)}^*bb+bb{(a+b)}^*aa]{(a+b)}^*$\ ? \\
Adjunk meg ehhez a nyelvhez egy determinisztikus véges automatát!
\\ \ \ \\
\end{document}

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




