\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{amssymb}
\usepackage{tabularx}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{fancyhdr}

\newtheorem*{defn}{Definíció}
\newcommand*{\term}[1]{\mbox{\texttt{#1}}}
\newcommand*{\nt}[1]{#1}
\newcommand*{\state}[1]{#1}
\newcommand*{\dir}[1]{\textrm{#1}}
\newcommand*{\set}[1]{\left\{\,#1\,\right\}}

\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 (8)}}
\\
\ \ 
\\
{\bf 2005. november 10., csütörtök}
\\
\ \ 
\\
\begin{enumerate}
\item  Adjunk véges fordítót, amely az alábbi dolgokat
  teszi: bemenetként \(\set{\term{a},\term{b}}\) feletti szavakat vesz, és
  átírja őket \(\set{\term{c},\term{d}}\) feletti szavakká úgy, hogy az
  \(\term{a}\)-t \(\term{c}\)-re, a \(\term{b}\)-t meg \(\term{d}\)-re
  cseréli.
\item Készítsünk véges fordítót az alábbi specifikáció
  alapján: legyen \(\Sigma=\set{\term{a},\term{b}}\). Ha az utoljára olvasott
  karakter megegyezik az azelőttivel, akkor írjon \\ \(\term{x}\)-et, ha
  különböznek, akkor írjon \(\term{y}\)-t. Az első karakter beolvasása után ne
  írjon semmit, így egy \(n\) hosszú szöveg fordítása \(n\)--1 hosszú lesz.
\item  A  2. feladatban szereplő
  fordítóval lefordítjuk azt a nyelvet, mely azon szavakból áll, ahol a
  szavakban a karakterek száma páratlan. Mi lesz a fordított nyelv automatája?
\item  A fordító ugyanaz, mint a 2.
  feladatban. A fordítandó nyelv: a szavak \(\term{a}\)-val kezdődnek,
  \(\term{b}\)-re végződnek, és a páros hosszú \(\term{b}\) sorozatok száma
  páratlan. Készíts a fordított nyelvre automatát!
\item Készítsünk szigorúan jellemző nyelvtant az
  1. feladatban leírt fordításhoz!
\item  Bizonyítsuk be, hogy ha egy fordításhoz van
  jellemző nyelvtan, akkor van hozzá szigorúan jellemző nyelvtan is!
\item Készítsünk olyan véges fordítót, mely minden \(w
  \in \set{\term{a},\term{b}}^*\) szó esetén annyi \(\term{x}\)-et ír ki,
  ahányszor a \(w\) szóban előfordul az \(\term{abaaba}\) részszó!  (Ha pl. \(w
  = \term{aabaabaababab}\), akkor \(\term{xx}\) lesz az eredmény, mert
  kétszer, a második és az ötödik pozíciótól kezdve szerepel az
  \term{abaaba} a \(w\) szóban.)
\item Készítsünk olyan fordító automatát, mely minden
  \(w \in \set{\term{a},\term{b}}^*\) szó esetén annyi nullát ír ki, ahány
  olyan \(x\) kezdőszelete van \(w\)-nek, hogy \(x\)-ben az \(\term{a}\)-k és a
  \(\term{b}\)-k száma azonos.
\item Adott az alábbi fordító automata:
\[
\begin{array}{ll}
\delta(\state{q}_0,\term{a})=(\state{q}_1,\varepsilon) &
\delta(\state{q}_0,\term{b})=(\state{q}_2,\varepsilon) \\
\delta(\state{q}_1,\term{a})=(\state{q}_0,\varepsilon) &
\delta(\state{q}_1,\term{b})=(\state{q}_0,\term{x}) \\
\delta(\state{q}_2,\term{a})=(\state{q}_0,\term{y}) &
\delta(\state{q}_2,\term{b})=(\state{q}_0,\varepsilon) 
\end{array}
\]

  Készíts automatát az \[\nt{S}\;\to\;\term{aa}\nt{S}\term{bb}\,|
  \,\term{b}\nt{S}\term{a}\,|\,\varepsilon\] nyelvtan
  által generált nyelv fordításának felismerésére!
\item Tekintsük az alábbi szintaxis vezérelt fordítási
  sémákat (\(\Sigma=\set{\term{a},\term{+},\term{*},\term{(},\term{)}}\) 
  \(\Delta=\set{\term{1},\term{2},\term{3},
  \term{4},\term{5},\term{6}}\)):
  \begin{enumerate}
  \item \(
    \begin{array}[t]{lclclcl}
      \nt{E}\,\to\,\nt{E}\term{+}\nt{T} & - & \term{1}\nt{ET} & & 
      \nt{E}\,\to\,\nt{T} & - & \term{2}\nt{T} \\
      \nt{T}\,\to\,\nt{T}\term{*}\nt{F} & - & \term{3}\nt{TF} & & 
      \nt{T}\,\to\,\nt{F} & - & \term{4}\nt{F} \\
      \nt{F}\,\to\,\term{(}\nt{E}\term{)} & - & \term{5}\nt{E} & & 
      \nt{F}\,\to\,\term{a} & - & \term{6}
    \end{array}
    \)
  \item \(
    \begin{array}[t]{lclclcl}
      \nt{E}\,\to\,\nt{E}\term{+}\nt{T} & - & \nt{ET}\term{1} & & 
      \nt{E}\,\to\,\nt{T} & - & \nt{T}\term{2} \\
      \nt{T}\,\to\,\nt{T}\term{*}\nt{F} & - & \nt{TF}\term{3} & & 
      \nt{T}\,\to\,\nt{F} & - & \nt{F}\term{4} \\
      \nt{F}\,\to\,\term{(}\nt{E}\term{)} & - & \nt{E}\term{5} & & 
      \nt{F}\,\to\,\term{a} & - & \term{6}
    \end{array}
    \)
  \end{enumerate}
  Mi a fordított nyelv?
\item Készíts olyan szintaxis vezérelt fordítási sémát, amely a száznál kisebb
  arab számokat római számokká írja át. Add meg a fordítás egy jellemző
  nyelvtanát is! 
\end{enumerate}
\end{document}








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












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

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