Emanuele Scapin - Automi di riconoscimento

Esempio 4: Dato l’automa rappresentato dal seguente diagramma, si individuare il linguaggio da esso riconosciuto di seguito si propone un programma che lo implementi.

E’ facile vedere e verificare che il linguaggio riconosciuto è L = { abⁿa | n ³ 0 }.

Il programma di seguito riportato data una stringa in ingresso stabilisce se appartiene o non al linguaggio L.

unit UAutomaRic;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons, StrUtils;

type
TFAutomaRic = class(TForm)
    txtStringa: TEdit;
    Label1: TLabel;
    btnEsci: TBitBtn;
    mmoAzioni: TMemo;
    Label2: TLabel;
    btnAvvio: TBitBtn;
    procedure btnEsciClick(Sender: TObject);
    procedure btnAvvioClick(Sender: TObject);
    procedure FormShow(Sender: TObject);
private
    m_iStato: integer; {0 = q0, 1 = q1, 2 = q2, 3 = q3}

    procedure Lettura;
    procedure StatoQ0(strCar: string);
    procedure StatoQ1(strCar: string);
    procedure StatoQ2(strCar: string);
    procedure StatoQ3(strCar: string);
    { Private declarations }
public
    { Public declarations }
end;

var
FAutomaRic: TFAutomaRic;

implementation

{$R *.dfm}

procedure TFAutomaRic.btnEsciClick(Sender: TObject);
begin
   Close();
end;

procedure TFAutomaRic.StatoQ1(strCar: string);
begin
   mmoAzioni.Lines.Add('q1');
   // Stabilisco cosa fare.
   if (strCar = 'a') then
   begin
      m_iStato := 2; // transito nello stato q2
      mmoAzioni.Lines.Add('transitato in q2');
   end
   else if (strCar = 'b') then
   begin
      m_iStato := 1; // permango nello stato q1
   end;
end;

procedure TFAutomaRic.StatoQ2(strCar: string);
begin
   mmoAzioni.Lines.Add('q2');
   // Stabilisco cosa fare.
   if ((strCar = 'a') or (strCar = 'b')) then
   begin
      m_iStato := 3; // transito nello stato q3
      mmoAzioni.Lines.Add('transitato in q3');
   end;
end;

procedure TFAutomaRic.StatoQ3(strCar: string);
begin
   mmoAzioni.Lines.Add('q3');
end;

procedure TFAutomaRic.StatoQ0(strCar: string);
begin
   mmoAzioni.Lines.Add('q0');
   // Stabilisco cosa fare.
   if (strCar = 'a') then
   begin
      m_iStato := 1; // transito nello stato q1
      mmoAzioni.Lines.Add('transitato in q1');
   end
   else if (strCar = 'b') then
   begin
      m_iStato := 3; // transito nello stato q3
      mmoAzioni.Lines.Add('transitato in q3');
   end;
end;

// Legge scandendo la stringa.
procedure TFAutomaRic.Lettura();
var
   ilunghezza: integer;
   strstringa: string;
   strcarattere:string;
begin
// Ne calcolo la lunghezza.
ilunghezza := length(trim(txtStringa.Text));
strstringa := trim(txtStringa.Text); // Tolgo eventuali spazi bianchi

// Fino a che la lunghezza e > 0 allora esamina
// altro carattere in ingresso.
while (ilunghezza > 0) do
begin
    // Prendo il carattere da esaminare e la parte restante della stringa.
    strcarattere := leftstr(strstringa, 1);
    strstringa := rightstr(strstringa, ilunghezza - 1);
    ilunghezza := length(strstringa);

    // Stabilisco cosa fare a seconda dello stato in cui sono.
    case m_iStato of
      0: StatoQ0(strcarattere);
      1: StatoQ1(strcarattere);
      2: StatoQ2(strcarattere);
      3: StatoQ3(strcarattere);
    end;
end;

// Stabilisco se la stringa è stata riconosciuta oppure no.
if (m_iStato = 2) then
    mmoAzioni.Lines.Add('Stringa riconosciuta')
else
    mmoAzioni.Lines.Add('Stringa NON riconosciuta');
end;

procedure TFAutomaRic.btnAvvioClick(Sender: TObject);
begin
   Lettura();
end;

procedure TFAutomaRic.FormShow(Sender: TObject);
begin
   // Lo stato di inizio è q0 = 0.
   m_iStato := 0;
end;

end.

Sono state implementate delle procedure, una per ogni stato, e all’interno di esse vengono stabilite le azioni da fare a seconda del carattere letto.
Per tenere a mente lo stato attuale in cui è l’automa si è ancora una volta inserito una variabile globale m_iStato, a seconda del valore assunto ci dice lo stato attuale
{0 = q0, 1 = q1, 2 = q2, 3 = q3}.

Si può migliorare il programma stabilendo la fermata non alla fine della scansione della stringa ma una volta individuato lo stato q3, che stabilisce che la stringa non è stata riconosciuta. Si può modificare il ciclo di lettura dei caratteri della stringa nel seguente modo, inserendo anche il controllo sul raggiungimento dello stato q3.

// Fino a che la lunghezza e > 0 allora esamina
// altro carattere in ingresso.
while ((ilunghezza > 0) and (m_iStato <> 3)) do
begin
    // Prendo il carattere da esaminare e la parte restante della stringa.
    strcarattere := leftstr(strstringa, 1);
    strstringa := rightstr(strstringa, ilunghezza - 1);
    ilunghezza := length(strstringa);

    // Stabilisco cosa fare a seconda dello stato in cui sono.
       case m_iStato of
      0: StatoQ0(strcarattere);
      1: StatoQ1(strcarattere);
      2: StatoQ2(strcarattere);
      3: StatoQ3(strcarattere);
    end;
end;

Il risultato in caso di riconoscimento della stringa.

Risultato nel caso di non riconoscimento.