\documentclass[10pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\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 Nehezebb/érdekesebb feladatok }
\\
\ \ 
\\
{\bf Általános és regulárisos feladatok}
\\
\ \ 
\\
1. (i) Adjunk 0-s nyelvtant az alábbi nyelvhez:
$\{x\in {\{a,b\}}^*\;|\;x$ nem $ww$ alakú $\}$ 
{\bf **}
\\
(ii)  Adjunk CF nyelvtant is hozzá.
{\bf *}
\\
\ \ 
\\
2.
Mutassuk meg, hogy minden DVA, ami elfogadja a ${(a+b)}^*a{(a+b)}^{n-1}$
nyelvet legalább $2^n$ állapotú, noha nemdeterminisztikus véges automata
már van $n+1$ állapottal is!
{\bf *}
\\
\ \ 
\\
3.
Nyelvtan kell az $\{a^{F(n)}\;|\;n\geq 1, F(n)$ az $n$-edik Fibonacci szám
$\}$ nyelvre. (Nem baj, ha 0-s lesz a nyelvtan)
{\bf **}
\\
\ \ \\
4.
Nyelvtan kell az $\{a^{p}\;|\;p$ prím szám
$\}$ nyelvre. (Itt se baj, ha 0-s lesz a nyelvtan, sőt mar az is jó, ha 
nagyjából el tudod mesélni, hogy hogyan működjön a nyelvtan, nem kell 
rögtön szabályokra lebontva leírni.)
{\bf ***}
\\
\ \ \\
5. 
Regulárisak-e az alábbi nyelvek?
\begin{enumerate}
\item  $L_1 = \{xx^Rw\;|\; x\in {\{0,1\}}^+, w\in {\{0,1\}}^*\}$
\item  $L_2 = \{xwx^R\;|\; x\in {\{0,1\}}^+, w\in {\{0,1\}}^*\}$
\end{enumerate}
Az egyik nem is csillagos, a másik meg {\bf **}. 
\\
\ \ \\
6.
Regulárisak-e a következő  nyelvek?
\begin{enumerate}
\item $\{0^i1^j \;|\; lnko(i,j)\not = 1\}$ {\bf **}
\item $\{0^{F(n)}\;|\; F(n)$ az $n$-edik Fibonacci-szám$\}$ {\bf *}
\end{enumerate}
\ \ 
\\
7.
Tegyük fel, hogy az $L_1$ nyelv reguláris, az $L_2$ nyelv pedig nem reguláris.
Igazoljuk, hogy ekkor $L_1L_2$ sem reguláris!
{\bf **}
\\
\ \ 
\\
8.
Legyen $L$ egy reguláris nyelv a $\Sigma$ ábécé felett. 
$0.5 \;L=\{x\in {\Sigma}^*\;|\;\exists y \in {\Sigma}^*, |y|=|x|, 
\;xy\in L\}$.
Azaz $0.5 \;L$-ben az $L$-beli szavak első felei vannak. Reguláris-e 
az $0.5 \;L$ nyelv?
\\
{\bf ** és fél *}
\\
\ \ 
\\
9. Bizonyítsd be, hogy ha $L\subseteq 0^*$ és $L$ CF nyelv, akkor $L$ 
reguláris is!
\\
{\bf Most éppen én se tudom, hogyan megy, valószínűleg igen nehéz = ****}
\\
\ \ \\ 
\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: 
