Formális nyelvek gyakorlat (8)

2005. november 10., csütörtök

  1. Adjunk véges fordítót, amely az alábbi dolgokat teszi: bemenetként \(\left\{\,\mbox{\texttt{a}},\mbox{\texttt{b}}\,\right\}\) feletti szavakat vesz, és átírja őket \(\left\{\,\mbox{\texttt{c}},\mbox{\texttt{d}}\,\right\}\) feletti szavakká úgy, hogy az \(\mbox{\texttt{a}}\)-t \(\mbox{\texttt{c}}\)-re, a \(\mbox{\texttt{b}}\)-t meg \(\mbox{\texttt{d}}\)-re cseréli.
  2. Készítsünk véges fordítót az alábbi specifikáció alapján: legyen \(\Sigma=\left\{\,\mbox{\texttt{a}},\mbox{\texttt{b}}\,\right\}\). Ha az utoljára olvasott karakter megegyezik az azelőttivel, akkor írjon
    \(\mbox{\texttt{x}}\)-et, ha különböznek, akkor írjon \(\mbox{\texttt{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.
  3. 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?
  4. A fordító ugyanaz, mint a 2. feladatban. A fordítandó nyelv: a szavak \(\mbox{\texttt{a}}\)-val kezdődnek, \(\mbox{\texttt{b}}\)-re végződnek, és a páros hosszú \(\mbox{\texttt{b}}\) sorozatok száma páratlan. Készíts a fordított nyelvre automatát!
  5. Készítsünk szigorúan jellemző nyelvtant az 1. feladatban leírt fordításhoz!
  6. Bizonyítsuk be, hogy ha egy fordításhoz van jellemző nyelvtan, akkor van hozzá szigorúan jellemző nyelvtan is!
  7. Készítsünk olyan véges fordítót, mely minden \(w \in \left\{\,\mbox{\texttt{a}},\mbox{\texttt{b}}\,\right\}^*\) szó esetén annyi \(\mbox{\texttt{x}}\)-et ír ki, ahányszor a \(w\) szóban előfordul az \(\mbox{\texttt{abaaba}}\) részszó! (Ha pl. \(w = \mbox{\texttt{aabaabaababab}}\), akkor \(\mbox{\texttt{xx}}\) lesz az eredmény, mert kétszer, a második és az ötödik pozíciótól kezdve szerepel az abaaba a \(w\) szóban.)
  8. Készítsünk olyan fordító automatát, mely minden \(w \in \left\{\,\mbox{\texttt{a}},\mbox{\texttt{b}}\,\right\}^*\) szó esetén annyi nullát ír ki, ahány olyan \(x\) kezdőszelete van \(w\)-nek, hogy \(x\)-ben az \(\mbox{\texttt{a}}\)-k és a \(\mbox{\texttt{b}}\)-k száma azonos.
  9. Adott az alábbi fordító automata:

    \begin{displaymath} \begin{array}{ll} \delta(q_0,\mbox{\texttt{a}})=(q_1,\vareps... ... & \delta(q_2,\mbox{\texttt{b}})=(q_0,\varepsilon) \end{array}\end{displaymath}

    Készíts automatát az

    \begin{displaymath}S\;\to\;\mbox{\texttt{aa}}S\mbox{\texttt{bb}}\,\vert \,\mbox{\texttt{b}}S\mbox{\texttt{a}}\,\vert\,\varepsilon\end{displaymath}

    nyelvtan által generált nyelv fordításának felismerésére!
  10. Tekintsük az alábbi szintaxis vezérelt fordítási sémákat ( \(\Sigma=\left\{\,\mbox{\texttt{a}},\mbox{\texttt{+}},\mbox{\texttt{*}},\mbox{\texttt{(}},\mbox{\texttt{)}}\,\right\}\) \(\Delta=\left\{\,\mbox{\texttt{1}},\mbox{\texttt{2}},\mbox{\texttt{3}}, \mbox{\texttt{4}},\mbox{\texttt{5}},\mbox{\texttt{6}}\,\right\}\)):
    1. \( \begin{array}[t]{lclclcl} E\,\to\,E\mbox{\texttt{+}}T & - & \mbox{\texttt{1... ...ttt{5}}E & & F\,\to\,\mbox{\texttt{a}} & - & \mbox{\texttt{6}} \end{array} \)
    2. \( \begin{array}[t]{lclclcl} E\,\to\,E\mbox{\texttt{+}}T & - & ET\mbox{\texttt... ...xttt{5}} & & F\,\to\,\mbox{\texttt{a}} & - & \mbox{\texttt{6}} \end{array} \)
    Mi a fordított nyelv?
  11. 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!