\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!
\\
\ \ \\
A mai óra anyaga:
\\
\ \ \\
1. Technikai megbeszélnivalók:\\
a jövő heti gyakorlat ugye elmarad, mert nov. 1. lesz. Helyette lesz egy 
alkalom, amire nem kötelező jönni: november 2., csütörtök, reggel (hajnal) 
fél kilenc, az I.B. 134-ben. \\
Nagyzh lesz nov. 8-án, a terembeosztást a jövő héten megmondom. Előtte
konzultáció lesz nov. 7-én 14.00-tól végkimerülésig, hogy hol azt majd megírom.
A nagyzh anyaga minden a reguláris és CF nyelvekkel, nyelvtanokkal kapcsolatban.
Mindent lehet használni, úgyhogy szerezzetek jegyzetet addigra!
\\
\ \ \\
2. Megbeszéltük a múlt heti 3c és 3d példákat.
\\ \ \ \\
3. Pumpálási lemma CF nyelvekre: Ha egy $L$ nyelv CF, akkor létzeik olyan
$N\geq 0$ szám, hogy minden olyan $w\in L$ szónak, melyre $|w|\leq N$
van olyan felbontása $w=uxyvz$ részre, hogy $ux^iyv^iz\in L$ és 
$xv\not =\epsilon$.\\
\ \ \\
Ezzel a lemmával beláttuk, hogy az $a^nb^nc^n$ nyelv nem CF.
\\
Pontosabban lásd a jegyzetben.
\\
\ \ \\
4. Veremautomata: definíció, üres veremmel és állapottal elfogadás. 
Megcsináltuk az 1. és 2. feladatot, HF a 3.
\\
\ \ \\
5. Előadáson lesz majd, hogy a veremautomaták és a CF nyelvtanok 
egyenértékűek, úgy értve ezt, hogy pontosan azok a nyelvek generálhatók CF 
nyelvtannal, amik veremautomatával elfogadhatók. Előadáson lesz vagy
volt két konstrukció, hogy hogyan kell CF nyelvtanhoz veremautomatát 
szerkeszteni. Ezekre a konstrukciókra vonatkozik az utolsó feladat, 
csináljátok meg.\\
\ \ \\
 
     {\large{\bf Formális nyelvek gyakorlat (7)}}
\\
\ \ 
\\
{\bf 2000. október  25., szerda}
\\\ \ \\
1. PDA kell ahhoz a nyelvhez, melynak ábécéje az $\{a,b\}$ és szavaiban az $a$ és 
a $b$ karakterek száma megegyezik. 
\\
\ \ 
\\
2. Automata kell:\\
$\{a^ib^jc^k\;|\;i+k=j\geq 0\;\}$ 
\\
\ \ 
\\
3. PDA kell a következő nyelvhez:\\
$\{a^mb^n\;|\;1\leq m\leq n\leq 2m\;\}$
\\
\ \ 
\\
4. 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.) 
\\
\ \ \\
5. Mutasd meg, hogy az 
$\{x\in {\{a,b,c\}}^*\;|\; {|x|}_a={|x|}_b={|x|}_c\}$ nyelv 
nem CF nyelv. \\
(Nehezebb feladat, a pumpálási lemmát kell élesíteni a megoldásához)
\\
\ \ 
\\
{\bf Gyakorolni még...}\\
\ \ \\
6. 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. 
\\
\ \ 
\\
7. 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. 
\\
\ \ 
\\
8. {\bf HÁZI FELADAT!!!}\\
Az $S\ra XY$, $X\ra aXb\;|\;ab$, $Y\ra bYc\;|\;bc$ nyelvtanhoz készítsünk 
PDA-t, mindkét konstrukcióval, amit tanultunk (vagy tanulni fogunk)! Elemezzük az 
$a^2b^5c^3$ szót mindkét automatával!\end{document}








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









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