% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{3. feladatsor, 13. feladat, adatabsztarkcióval}
\begin{document}
\noindent
\emph{Feladat:} Az $x$ sorozat egy szöveget tartalmaz.  Tömörítsük a
szöveget úgy, hogy mindenütt, ahol több szóköz van egymás mellett,
csak egy szóközt hagyjunk meg!

\emph{Specifikáció:}\\
$X = \seq(Ch)$\\
$A = \alatt{X}{x} \times \alatt{X}{y}$\\
$B = \alatt{X}{x'}$

Ezen az állapottéren nem tudnánk visszavezetni a feladatot, ezért az
$x$-et transzformáljuk egy olyan $z\in Z$ sorozattá, amiben a szóközök
csak csoportosan (szóközök sorozataként) fordulhatnak elő, azaz a $Z$
sorozattípus, $S$ alaptípusa egy olyan egyesítés lesz, aminek minden eleme
nem szóköz karakter vagy $E$ típusú szóközsorozat:

$Ch' = Ch\setminus\{\_\}$\\
$E = \seq^+(\{\_\}), S = (s:Ch';e:E), Z=\seq(S)$\\
$I_Z(z) = \forall i\in[1,\dom(z)-1]: z_i.e \nyil z_{i+1}.s$\\
$A' = \alatt{Z}{z} \times \alatt{X}{y}$\\
$\seq(z|Ch)=\seq(x|Ch)$

\vspace{2cm}

Az invariánssal azt zártuk ki, hogy szóközcsoportok kövessék egymást
közvetlenül.  A szekvenciális megfelelővel pedig könnyedén fel tudtuk
írni a két állapottér közti összefüggést, nevezetesen azt, hogy a
szöveget lényegében nem rontottuk el, csak a struktúráját változtattuk
meg.

Ezen az állapottéren már könnyebb lenne felírni a megoldóprogramot,
csak ezt a transzformációt macerás megvalósítani az unió miatt,
könnyebb dolgunk van, ha a szóközcsoportok helyett csak egy szóköz
szerepel.  Ez a transzformáció az előzőnél is egyszerűbb:

$T = \file(Ch)$\\
$A'' = \alatt{T}{t} \times \alatt{X}{y}$\\
$B'' = \alatt{T}{t'}$\\
$\dom(t)=\dom(z) \es \forall i\in[1,\dom(t)]: z_i.e\nyil t_i=\_ \es z_i.s\nyil t_i=z_i$

Példa:
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
x: & a & l & m & a & \_ & \_ & a & \_   & b & o & k & o & r & b & a & n & \_& \_&\_\\
\hline
z: & a & l & m & a & <\_,\_> & a & <\_> & b & o & k & o & r & b & a & n & <\_,\_,\_>\\
\hline
t: & a & l & m & a & \_ & a & \_ & b & o & k & o & r & b & a & n & \_
\end{tabular}

Ezen az állapottéren a megoldás az elemenkénti feldolgozás, identikus leképezéssel.

$Q = ( t=t' )$\\
$R = ( y=t')$

Az alábbiakban megadjuk az új absztrakt állapottéren működő
visszavezetéssel kapott programot és a konkrét filet absztrakttá
``alakító'' programrészleteket.  Ezt a módszert adatabsztrakciónak
hívjuk.

\begin{stuki}[6cm]
  \stm{st,dt,t:\Read}
  \stm{y:=<>}
  \begin{WHILE}{2}{\stm{st}}
    \stm{y:\hiext(dt)}
    \stm{st,dt,t:\Read}
  \end{WHILE}
\end{stuki}

\begin{textblock}{1}(5.0,-10.5)
\begin{stuki*}{$st,dt,t:$read}
  \begin{IF}[80]{5}{\stm{x.\dom\ne 0}}
    \stm{st:=\norm}
    \stm{dt:=x.\lov}
    \begin{IF}{2}{\stm{dt=\_}}
      \begin{WHILE}{1}{\stm{x.\dom\ne 0\es x.\lov=\_}}
        \stm{x:\lorem}
      \end{WHILE}
      \ELSE
      \stm{x:\lorem}
    \end{IF}
    \ELSE
    \stm{st:=\abnorm}
  \end{IF}
\end{stuki*}
\end{textblock}

\end{document}