\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
Sziasztok!
\\
\ \ \\
Hirdetnivalók: \\
1.A nagy zh terembeosztása:\\
A-D : E. I. C.\\
E-F meg a németesek : I.B. 027\\
G-Ó : St. Nagy
P-végig : E.I.B
\\
A zh-n minden korábban készült írásos segédeszköz használható, 
számológépek, mobiltelefonok nem.
\\
2. A zh előtt konzi az én csoportjaimnak: nov. 7. kedd, 14.00-tól az 
E. I. C.-ben.
\\
3. Aki jönne a héten csütörtök reggel konzultálni, az ne tegye, mert a szerdai csoportnak lesz
akkor pótóra.
\\
\ \ \\
Az óra anyaga: \\
1. Az előadáson tanult két konstrukció arra, hogy hogyan kell
CF nyelvtanból a nyelvtan által generált nyelvet elfogadó
veremautomatát csinálni. Ennek a'tismétlése, majd a múltkori feladatsor utolsó 
példájának megoldása. \\
\ \ \\
2. Említve, hogy visszafele is megy a konstrukció: PDA-ból is lehet CF nyelvtant
csinálni, előadáson volt a konstrukció, a példát nézzétek meg a jegyzetben.
(Ugye már megszereztétek?)
\\
\ \ \\ 
3. Feladatmegoldás, önállóan. A múltkoriból kimaradt feladatok, meg a mostaniak.
Megbeszéltük a múltkori 3. és 6.-nak az elvét, meg a mostani 2.-at.
\\
\ \ \\
4. Van nehéz feladatsor is, be lehet adni a megoldásokat lapon. De be lehet adni
bármilyen megoldást is lapon, ha azt szeretnbétek, hogy megnézzem.
\\
\ \ \\
{\large{\bf Formális nyelvek gyakorlat (8)}}
\\
\ \ 
\\
{\bf 2000. október  30., hétfő}
\\\ \ \\
1. Mi lenne, ha két vermet engednénk mega veremautomatában? 
Azaz, ha a veremautomata szabályai 
$Q\times(\epsilon\cup \Sigma)\times {\Gamma}_1\times {\Gamma}_2\ra Q\times 
{{\Gamma}_1}^*\times {{\Gamma}_2}^*$ alakúak volnának?
Növekedne-e az automata ereje?
\\
(Az $a^nb^nc^n$ nyelv nem CF.)
\\
\ \ 
\\
2. Az ismert $E\ra E+T\;|\;T$, $T\ra T*F\;|\;F$, $F\ra (E)\;|\;a$ nyelvtan generál 
felesleges zárójeleket. Például az $(a*a)+a$ generálásakor.
Alakítsuk át úgy a nyelvtant, hogy ne tegye ezt!
\\
\ \ \\
{\bf Cseles kérdések:}\\
\\
\ \ 
\\
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 Megszámlálhatóan végtelen sok reguláris nyelv van
\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)}^*$
\item Ha $L$ reguláris, akkor az $L'=\{ww\;|\;w\in L\}$ nyelv is reguláris, hiszen 
$L'=L^2$
\item Ha $L$ reguláris, akkor $L^{-1}$ is reguláris
\item Ha $L$ egy reguláris nyelv a $\Sigma$ ábécé felett, akkor az 
$L'=\{w\in{\Sigma}^*\;|\;\exists x\in L:|x|=|w|\}$  nyelv is reguláris.
\item Ha $M$ egy PDA, akkor $L_u=L_a$, ahol $L_u$ azon nyelv, amit az automata 
üres veremmel elfogad, míg $L_a$ az a nyelv, amit végállapottal elfogad.
\item Ha $L$ egy CF nyelv és $\epsilon\in L$, akkor van olyan $L$-t generáló 
nyelvtan, ami pontosan egy $\epsilon$-szabályt tartalmaz.
\end{enumerate}
\end{document}

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



