\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\newcommand{\ra}{\ensuremath{\rightarrow}}
\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: (a módszerek pontosan le vannak írva a jegyzetben)
\\
\ \ \\
1. Chomsky normál formára hozás: ez azt jelenti, hogy elérjük, hogy a 
CF (környezetfüggetlen) nyelvtan minden szabálya $A\ra a$ vagy $A\ra BC$ 
alakú legyen, ahol $A,B,C\in N$ és $a\in \Sigma$. (Meg esetleg lehet még 
$S\ra \epsilon$ szabály is, de ekkor $S$ nem szerepelhet szabály jobboldalán) 
(Persze mindezt úgy, hogy a generált nyelv ne változzon.)
\\
Ehhez gyakorló példa a múltkori feladatsor 8. feladata.
\\
\ \ \\
2. A közvetlen balrekurzió kiküszöbölése: Egy nyelvtan rekurzív, ha van olyan 
$A\in N$ nemterminális, hogy $A{\Ra}^+\ldots A\ldots$,  azaz, ha $A$-ból le 
lehet vezetni olyan szót, amiben $A$ szerepel. Ezt nem lehet megszüntetni 
úgy, hogy alakítgatjuk a nyelvtant, mert a nyelvtan rekurzív volta azzal 
ekvivalens, hogy a generált nyelv végtelen. (Meggondolni esetleg!!)
\\
Meg lehet viszont szüntetni egy nyelvtan balrekurzivítását, azaz azt, hogy
legyen olyan $A\in N$ nemterminális, hogy $A{\Ra}^+A\ldots$,  
azaz, hogy $A$-ból le lehessen vezetni olyan szót, ami $A$-val kezdődik.
(Ezt azért fontos megszüntetni, mert az elemzők nagy része, amiket használunk,
nem megy, ha a nyelvtan balrekurzív.)
\\
Először az úgynevezett közvetelen balrekurziót küszöböljük ki:
ez az, hogy van a nyelvtanban $A\ra A\alpha$ szabály, azaz olyan szabály, 
ahol a jobboldal ugyanavval a nemterminálissal kezdődik, ami a baloldalon áll.
\\
Ehhez gyakorló példa a múltkori sor 9. feladata.
\\
\ \ \\
3. Greibach normál formára hozás: ez azt jelenti, hogy csak $A\ra aW$ 
alakú szabályokat akarunk (meg persze esteleg $S\ra \epsilon$, de akkor...),
ahol $A\in N, a\in \Sigma, W\in N^*$. Azaz azt akarjuk, hogy minden szabály
jobboldala terminálissal kezdődjön. 
(Ez megoldja a balrekurzió problémáját is, látjátok, ugye?)
\\
Ehhez feladatok a mostani 1. és a gyakorlós 5. feladat.
\\\ \ \\
4. Felelevenítettük az előadásról a levezetési fa, jobb és ballevezetés, 
egyértelmű, nem egyértelmű CF nyelvtan /CF nyelv fogalmakat. Ezekhez van
a többi példa. Órán volt a 2. és a 3b nagyjából. A 3d-t megbeszéljük, a többit
majd, ha kéritek.    
\\
\ \        
\\
{\large{\bf Formális nyelvek gyakorlat (6)}}
\\
\ \ 
\\
{\bf 2000. október  18., szerda}
\\
\ \ 
\\
1. GNF kell:
$S\ra AS\;|\; b$, $A\ra SA\;|\;aa$
\\
\ \ 
\\
2. 
(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!)\\
\ \ 
\\
3. 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$
\\
\ \ 
\\
4. 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!
\\
\ \ 
\\
{\bf Gyakorlásnak...}
\vspace*{.5cm}\\
5. GNF kell:
$A\ra BC$, $B\ra CA|b$, $C\ra AB|a$
\\
\ \ 
\\
6. 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!
\\
\ \ \\
7. 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?
\\
 \ \ \\
8. 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?
\\
\ \ 
\\
9. 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.
\\
A posztfix  nyelvtant add meg GNF-ban is!

\end{document}








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












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