\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 (6)}}
\\
\ \ 
\\
{\bf 2005. október  27., csütörtök}
\\
\ \ 
\\
1 . Küszöböljük ki a felesleges szimbólumokat!\\
$S\ra a|B$, $B\ra BC$, $C\ra b$ 
\\
\ \ 
\\
2.  Küszöböljük ki a felesleges szimbólumokat!\\
$S\ra A|B$, $A\ra aB|bS|b$, $B\ra AB|Ba$, $C\ra AS|b$
\\
\ \ 
\\
3. Mi lenne, ha az 1. feladatban előbb csinálnánk a 
top-down fésülést?
\\
Tanulság: A sorrend nem mindegy.
\\
\ \ 
\\
4. (Szigorlaton lehet ilyen kérdést kapni)
\\
Miért a gyakorlaton nézett sorrendben kell elvégezni a jólfésülés három részét?
(Azaz ha máshogy csinálnánk, akkor az miért lenne rossz, 
illetve így miért nem az?) 
\\
\ \ 
\\
5. Jólfésült nyelvtan kell ebből:
$S\;\ra \; Ba\;|\;Cab\;|\;A$,\\
$A\;\ra \; aB\;|\;aC\;|\;a$,\\
$B\;\ra b\;|\;BC$,\\
$C\;\ra \;Cb\;|\;CA$
\\
\ \ 
\\
6. 
(a) Rajzoljuk fel a $aaa*a+a+*$ 
szó egy levezetési fáját az $E\ra EE+\;|\;EE*\;|\;a$ 
nyelvtanban! Adjuk meg a fához tartozó jobb és ballevezetést! 
Egyértelmű-e ez a nyelvtan?
\\
(b) Írjuk át az $aaa*a+a+*$ posztfix alakú kifejezést infix alakba!
(Használjuk a levezetési fát!)\\
\ \ 
\\
7. Mit generálnak az alábbi nyelvtanok?
Egyértelműek-e a nyelvtanok?
\\
(a) $S\ra aSb|\epsilon$
\\
(b) $S\ra SaSb|\epsilon$
\\
(c) $S\ra SaSbS|\epsilon$
\\
(d)
$S\ra SaSbSa|\epsilon$
\\
\ \ 
\\
8. Egészítsük ki az infix aritmetikás egyértelmű nyelvtant a hatványozással
($\wedge)$!
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!
\\
\ \ 
\\
9. Tekintsük a következő $G$ nyelvtant: \\
$S \ra A \mid B \mid bbS$,\ \  $A \ra aB \mid bSA \mid b$, \ \ 
$B \ra AB \mid BC$, \ \ $C \ra AS \mid bB \mid a$ \\
(a) Egyértelmű-e a $G$ által  generált nyelv? \\
(b) Egyértelmű-e a $G$ nyelvtan?
\\
 \ \ \\
10. Adott két nyelv: \\
$L_1=\{\;w\in {\{a,b\}}^*\;|\; 3\;|\;{|w|}_a, 4\;|\;{|w|}_b\;\}$, 
$L_2= \{\;w\in {\{a,b\}}^*\;|\; w=w^R\;\}$\\ 
Készítsen nyelvtant $L_1\cap L_2$-re!
\\
\ \ \\
11. Vegyük a következő nyelvtant, ahol az $if$, $then$ és $else$ szavak a 
nyelvtan terminális szimbólumai:
\\
$S\ra if\;\;E\;\;then \;\;S\;|\;if \;\;E\;\;then\;\;S\;\;else\;\;S\;|\;a$,
$E\ra b$.
\\
(a) Egyértelmű-e a nyelvtan?
\\
(b) Egyértelmű-e a generált nyelv?
\\
\ \ 
\\
12. Az infix alakú aritmetikai kifejezések helyett néha
célszerűbb a prefix vagy posztfix lengyel jelölés használata. Például a csak 
összeadást és szorzást használó posztfix lengyel aritmetikai kifejezéseket
az alábbi nyelvtan generálja:\\
$E\ra EE+|EE*|a$\\
Készíts két egyértelmű nyelvtant, egyet a posztfix egyet meg az infix 
alakú Boole-kifejezések generálására, ahol az operátorok a következők:
$\neg$ monadikus, $\cup$ és  $\cap$ diadikus operátorok, 
ebben a precedencia-sorrendben. A diadikusok balról-jobbra értékelődnek ki.
 A precedencia zárójelekkel 
felülbírálható, két monadikus operátor nem állhat egymás mellett.

\end{document}








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












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