\documentclass[12pt]{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 2001. február 13., kedd}
\\
\ \ 
\\
1.
Adjunk olyan nyelvtant, amely azon $\{a,b\}$ feletti szavakat generálja, 
melyek\\
(a) $a$-val kezdődnek
\\
(b) $a$-val kezdődnek és $b$-vel végződnek
\\
(c) nem ugyanazzal a betűvel kezdődnek, amivel végződnek
\\
\ \ 
\\
2. 
\\
(a) Adjunk generatív nyelvtant, 
amely a $\{w_1,\ldots,w_n\}$ véges nyelvet generálja!\\
(b) A fenti nyelvhez adjunk reguláris nyelvtant.
\\
\ \ 
\\
3. 
Adjunk minél egyszerűbb (alacsonyabb osztályú) nyelvtant ahhoz a nyelvhez, 
ami azon szavakat tartalmazza, melyek 
tartalmazzák a $baba$ részszót!
\\
\ \ 
\\
4. 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\;|\;m\leq n\leq 3m\;\}$
\\
\ \ 
\\
5. Mit generál az alábbi nyelvtan?
\\
$S\;\ra \; aS\;|\;bS\;|\;cS\;|\;cA$, $A\;\ra \; cB$, $B\;\ra \; 
aB\;|\; bB\;|\;cB |\; \epsilon$ 
\\
\ \ 
\\
6. Mi a generált nyelv?
\\
$S\ra AB | \epsilon $, $A\ra aAb | \epsilon$, $B\ra bBc | \epsilon$
\\
\ \ 
\\
7. 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*}
Adja meg a generált nyelvet és ismertesse a nyelvtan gondolatmenetét!
\\
\ \ 
\\
{\bf Nehezebb, de érdekes feladat}
\\
\ \ 
\\
8. 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.)
\end{document}

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




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