\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}
\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 Formális nyelvek gyakorlat (9)}}
\\
\ \ 
\\
{\bf 2001. április 10., kedd}
\\
\ \ 
\\
1. \\
(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?
\\
(c) Készíts ballevezetést a $+*aaa$ szóhoz a nyelvtanban és ezt vesd össze a
PDA elfogadó működésével!
\\
\ \ \\
2. \\
(a) 
Adj veremautomatát az $E\ra EE+\;|\;EE*\;|\;a$ nyelvtanhoz az órán tanult 
második konstrukcióval (ami röntgenszemű PDA-t ad).
\\
(b) Adj egy elfogadó lépéssorozatot az $aa+a*$ szóhoz a PDA-ban!
Adj egy nem elfogadót is! Hogy működik a PDA a $+a*$ szón?
\\
(c) Készíts jobblevezetést az $aa+a*$ szóhoz a nyelvtanban és ezt vesd össze a
PDA elfogadó működésével!
\\
\ \ 
\\
3. 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\}$ 
\\
\ \ 
\\
4. Determinisztikus PDA kell a következő nyelvekhez:\\
$L_1=\{a^mb^nc^n\;|\;0\leq m, n\;\}$\\
$L_2=\{a^mb^mc^n\;|\;0\leq m, n\;\}$
\\
\ \ 
\\
5. Igaz-e, hogy minden PDA-hoz lehet vele egyenértékű egyálapotú PDA-t adni?
\\
\ \ \\
6. Igaz-e, hogy minden olyan $P$ PDA-ra, melynek vannak elfogadó állapotai 
az automata által üres veremmel elfogadott nyelv megegyezik az automata által
állapottal elfogadott nyelvvel?
\\
\ \ \\
7. Egészítsük ki az infix aritmetikás egyértelmű nyelvtant a hatványozással
($\wedge)$! \\
(A nyelvtan: $E\ra E+T\;|\;T$, $T\ra T*F\;|\;F$, $F\ra (E)\;|\;a$) 
\\
Ennek a precedenciája a legnagyobb és jobbról-balra szabály szerint 
értékelődik ki. Adjuk meg a nyelvtant és az $(a+a)\wedge a*a$ kifejezés levezetési
fáját!
\ \ \\
\end{document}

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




