\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\newcommand{\ra}{\ensuremath{\rightarrow}}


\setlength{\textheight}{26cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-3cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\noindent
{\large{\bf Formális nyelvek gyakorlat (7)}}
\\
\ \ 
\\
{\bf 2005. november 3., csütörtök}
\\
\ \ 
\\
1. PDA kell ahhoz a nyelvhez, melynek ábécéje az $\{a,b\}$ és szavaiban az $a$ és 
a $b$ karakterek száma megegyezik. 
\\
\ \ 
\\
2. Automata kell (első kérdés, hogy milyen?):\\
$\{a^ib^jc^k\;|\;i+k=j\geq 0\;\}$ 
\\
\ \ 
\\
3. Determinisztikus PDA kell a következő nyelvhez:\\
$L_1=\{a^mb^nc^n\;|\;1\leq m, n\;\}$
\\
\ \ \\
4. Az $L_1$ és az $L_2$ nyelveket is az definiálja, hogy bennük az $ab$ és a $ba$
minirészsorozatok száma azonos. Viszont $L_1$ ábécéje az $\{a,b\}$, $L_2$-é
pedig az $\{a,b,c\}$. Mindkét nyelvre kell automata vagy nyelvtan. 
\\ \ \ \\
5. PDA kell a következő nyelvhez:\\
$\{a^mb^n\;|\;1\leq m\leq n\leq 2m\;\}$
\\ \ \ \\
6. Tervezzen automatát azon $\Sigma=\{a,b\}$ feletti nyelvhez,
melynek szavaiban a magányos b-k száma meghaladja az egynél hosszabb
homogén a sorozatok számát. 
\\ \ \ \\
7. A kétirányú PDA, olyan mint a sima PDA, csak bír visszafele is menni.
(Ahogy a 2VA-nál volt.) Akkor fogad el, ha végigolvassa a szót és elfogadó 
állapotba kerül. Kérdés: erősebb-e ez, mint a sima PDA?
\\
(Segítség: az $a^nb^nc^n$ nyelv nem CF nyelv.)
\\ \ \ \\
8. (a) 
Adj veremautomatát az $E\ra +EE\;|\;*EE\;|\;a$ nyelvtanhoz az órán tanult 
első konstrukcióval (ami nem röntgenszemű PDA-t ad).
\\
(b) Adj egy elfogadó lépéssorozatot a $+*aaa$ szóhoz a PDA-ban!
Adj egy nem elfogadót is! Hogy működik a PDA a $+*a$ szón?
\\ \ \ \\
9. Környezetfüggetlen-e az alábbi nyelv?
(Ha igen, akkor adj PDA-t hozzá, ha nem, akkor bizonyítsd be ezt!)\\
$L=\{a^ib^jc^k\;|\;0\leq i\leq j\leq k\}$
\\  \ \ \\
10. Igazak-e az alábbi állítások?
Az indoklás nem elhanyagolható része a válasznak.
\begin{enumerate}
\item Minden többállapotú PDA-hoz létezik vele egyenértékű egyállapotú PDA. 
\item Egy reguláris nyelv minden részhalmaza reguláris.
\item Ha az $L_1, \ldots ,L_n$ nyelvek ($n\geq 1$) regulárisak, akkor az 
${\cup}_{i=1}^nL_i$ nyelv is reguláris.
\item Megszámlálhatóan végtelen sok reguláris nyelv uniója nem feltétlenül 
reguláris
\item Megszámlálhatóan végtelen sok reguláris nyelv uniója lehet 
reguláris
\item Attól. hogy $L_1$ és $L_2$ nem reguláris, $L_1\cup L_2$ még lehet reguláris
\item $(r^*+s^*)(s^*+r^*)={(r+s)}^*$
\end{enumerate}
\end{document}








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












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