\documentclass[10pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\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}}
\\
\ \ 
\\
{\bf 2005. szeptember 15., csütörtök}
\\
\ \ 
\\
1.
Milyen nyelvet ír le az alábbi kifejezés?
\\
(a) ${(a+b)}^*(aa+bb){(a+b)}^*=$
\\
(b) ${(ab)}^+=$  
\\
\ \ 
\\
2. Mit generál az alábbi nyelvtan?
\\
$S\;\ra \; aS\;|\;bS\;|\;cS\;|\;cA$, $A\;\ra \; cB$, $B\;\ra \; 
aB\;|\; bB\;|\;cB |\; \epsilon$ 
\\
\ \ 
\\
3. Na és ez?
\\
$S\ra aSBC\;|\;abC, CB\ra BC, bB\ra bb, bC\ra bc, cC\ra cc$
\\
\ \ 
\\
4. 
(i) Adjunk generatív nyelvtant, 
amely a $\{a,ab,bbb,ba\}$ véges nyelvet generálja!\\
(ii) A fenti nyelvhez adjunk reguláris nyelvtant.
\\
(iii) Igaz-e, hogy minden véges nyelv reguláris? 
\\
\ \ 
\\
5. 
Adjunk minél egyszerűbb (alacsonyabb osztályú) nyelvtant ahhoz a nyelvhez, 
ami azon szavakat tartalmazza, melyek a $\Sigma=\{a,b\}$ ábécé felett
vannak és 
\\ (a) tartalmazzák a $baba$ részszót!
\\  (b) páros hosszúak!
\\
\ \ 
\\
6. Adjuk meg CF nyelvtannal az alábbi nyelveket!
\\
(a) $\{{a^nb^n}\;|\;n\geq 0\;\}$                  
\\
(b) $\{a^ib^ic^j, a^{i}b^jc^j\;|\;i,j\geq 1\;\}$
\\
(c) $\{a^mb^n\;|\;0\leq m\leq n\leq 3m\;\}$
\\
\ \ 
\\
7. Mi a generált nyelv?
\\
$S\ra AB | \epsilon $, $A\ra aAb | \epsilon$, $B\ra bBc | \epsilon$
\\
\ \ 
\\
8. Adott az alábbi nyelvtan:
\begin{eqnarray*}
S& \ra & BXB\\
X&\ra&CXA\;|\;\epsilon \\
CA & \ra &aAC  \\
Ca  & \ra &aC  \\
CB  & \ra &aB  \\
Ba  & \ra & aB \\
BA  & \ra &aB\\
BB  & \ra &a  
\end{eqnarray*}
Add meg a generált nyelvet és ismertesd a nyelvtan gondolatmenetét!
\\
\ \ 
\\
9. Adott véges ábécé felett 
\\
(a) hány generatív grammatika van?
\\
(b) hány generatív nyelv van?
\\
(c) hány reguláris nyelv van?
\\ \ \ \\
{\bf Nehezebb, de érdekes feladatok}
\\
\ \ 
\\
10. Keressünk CF nyelvtant az alábbi nyelvhez:
$\{x\in {\{a,b\}}^*\;|\;x$ nem $ww$ alakú $\}$ 
\\
(Ha CS-t sikerül adni, az se rossz.)
\\ \ \ \\
11. Nemcsökkentőnek nevezünk egy nyelvtant, ha benne minden szabály
baloldala legfeljebb olyan hosszú mint a jobboldala (kivéve esetleg
az $S\ra \epsilon$ szabályt, de ha ilyen van a nyelvtanban, akkor az
$S$ nem sze\-re\-pelhet szabály jobboldalán). Bizonyítsd be, hogy a
nemcsökkentő nyelvtanok éppen a környezetfüggő nyelveket generálják.

\end{document}

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



