\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 CF-es feladatok}
\\
\ \ 
\\
1. Mutasd meg, hogy egy $L$ nyelv elfogadható üres veremmmel elfogadó 
{\it determinisztikus} PDA-val pontosan akkor, ha elfogadható állapottal elfogadó
{\it determinisztikus} PDA-val {\bf és} a nyelv prefix tulajdonságú!
{\bf **}
\\
\ \ \\
2. Veszítenének-e a PDA-k az erejükből, ha megtiltanánk az $\epsilon$-
mozgásokat? Ez két kérdés: mi van az állapottal elfogadás és mi van az üres
veremmel elfogadás esetén?
{\bf ***}
\\
\ \ \\
3. Az $\{x\in {\{a,b,c\}}^*\;|\; {|x|}_a={|x|}_b={|x|}_c\}$ nyelv nem CF nyelv.
\\
(A pumpálási lemmát kell élesíteni)
\\
{\bf **}\\
\ \ 
\\
4. Az $L=\{a^ib^ic^j\;|\;i,j\geq 1, i\not= j\}$ nyelv nem CF nyelv.
\\
(Itt is célhoz vezet a lemma élesítése)
\\
{\bf **}
\\
\ \ 
\\
5.(a) Az $\{a^nb^n\;|\;n\geq 1\}\cup\{a^nb^{2n}\;|\;n\geq 1\}$ nyelv CF. \
Lásd be ezt!
\\
(b) Bizonyítsd be, hogy nem lehet determinisztikus PDA-val elfogadni!
\\
{\bf Sok csillag = nem tudom a megoldását }
\\
\ \ 
\\
6. Mutasd meg, hogy az 
$\{0^n1^m2^n\;|\;n,m\geq 1\}\cup\{0^n1^{m}2^m\;|\;n,m\geq 1\}$ nyelvet
nem lehet determinisztikus PDA-val elfogadni!
\\
(Valószínűleg hasonlóan megy, mint az előző)\\
{\bf Sok csillag = nem tudom a megoldását}
\\
\ \ \\ 
7. CF nyelvek-e az alábbiak?\\
(a) $\{a^nb^m\;|\;n\not =m$ és $n\not =2m\}$\\
(b) ${(a+b)}^*\setminus \{{(a^nb^n)}^n\;|\;n\geq 1\}$,
\\
(c) $\{ww^{-1}w\;|\;w\in {(a+b)}^*\}$\\
{\bf *}
\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: 

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