program KSP845;         { Konecne automaty v case O( n ) }

const MaxDelka = 200;    { Maximalni delka slova }

var delta : array [0..2*MaxDelka] of   { Netrivialni slozka prechodove funkce }
            record
               znak : char;          { Znak pro tento prechod }
               kam : integer;        { Kam se prejde }
            end;
  pocdelta : integer;                { Pocet polozek v poli delta }
  stavy : array [0..MaxDelka] of     { Informace pro jednotlive stavy }
            record
              bdelta: integer; { Zacatek useku prechodove funkce v poli delta pro tento stav}
              ndelta: integer; { Delka useku prechodove funkce v poli delta pro tento stav}
              ekviv : integer; { Cislo nejdelsiho kratsiho "ekvivalentniho stavu}
            end;
  stav : integer;        { Pomocna promenna }
  i,j : integer;         {    - " -         }
  s : string;            { Vstupni slovo, pro ktere vytvarime KA }

begin
   repeat                { Nacteme vstup }
   write('Zadej vstupni slovo : ');readln(s);
   until (s<>'') and (length(s)<MaxDelka);

   stavy[0].bdelta:=0;   { Delta pro nulty stav }
   stavy[0].ndelta:=1;
   delta[0].znak:=s[1];
   delta[0].kam:=1;
   pocdelta := 1;

   stavy[1].ekviv:=0;      { Prvni stav je ekv. nultemu }
                     { Spocteme prechodovou funkci v ostatnich stavech krome posledniho }
   for stav:=1 to length(s)-1 do
    begin
       stavy[stav+1].ekviv:= 0; { Nastavime ekviv dalsiho stavu prozatim na nulu }

       stavy[stav].bdelta:= pocdelta;  { Nastavime pocatecni hodnoty }
       stavy[stav].ndelta:= 1;
                               { Nastavime implic. prech. fci. tohoto stavu }
       delta[pocdelta].znak := s[stav+1];
       delta[pocdelta].kam  := stav+1;
       pocdelta := pocdelta+1;

       { Prechodova funkce je az na s[stav+1] stejna jako ekviv }
       for i:=stavy[stavy[stav].ekviv].bdelta to
         stavy[stavy[stav].ekviv].bdelta + stavy[stavy[stav].ekviv].ndelta - 1 do
                     { Pokud ma ekv. stav prechod pro s[stav+1], }
                     { pak je to ekv. nasledujiciho stavu }
          if delta[i].znak = s[stav+1] then stavy[stav+1].ekviv := delta[i].kam
          else
           begin     { Jinak nastavime rechodovou funkci tohoto stavu }
              delta[pocdelta]:=delta[i];
              stavy[stav].ndelta := stavy[stav].ndelta + 1;
              pocdelta := pocdelta + 1;
           end;
    end;

   { Vystup }
   writeln('Konecny automat pro toto slovo je tento:');
   writeln('KA = ( { predepsana abeceda }, Q, delta, D0, { D',length(s),' } )');
   writeln(' Q = { D0 .. D',length(s),' }');

   for stav:=0 to length(s)-1 do
      for i:=stavy[stav].bdelta to stavy[stav].bdelta+stavy[stav].ndelta - 1 do
         writeln('delta( D',stav,' ''',delta[i].znak,''' ) = D',delta[i].kam);
   writeln('delta( D',length(s),', pro vsechny znaky ) = D',length(s));
   writeln('Vsechny vyse neuvedene prechody jsou do stavu D0');
end.