Automate finite

Temă pentru laborator

1. Construiți un automat care acceptă texte care corespund programelor C cu următoarele restricții:

Programul nu se poate termina în mijlocul unui comentariu, constante caracter sau șir.
Constantele caracter sunt scrise între apostroafe, iar cele șir între ghilimele. Apostroafele și ghilimelele pot fi incluse în constante șir sau caracter dacă sunt precedate de backslash \ .
Într-o constantă șir, caracterele /* nu sunt considerate început de comentariu.

2. Scrieți un automat nedeterminist pentru limbajul cu simboluri 0 și 1, și care acceptă toate cuvintele pentru care al treilea simbol de la sfârșit e 1. Construiți un automat determinist echivalent.

Citirea descrierii unui automat

Citim de la intrare un automat descris sub formă de graf în format dot . Putem scrie automatul ca graf orientat: o muchie reprezinta o tranzitie dintr-o stare in alta stare, etichetata cu simbolul de intrare.

De exemplu, următoarea descriere reprezintă automatul din figură.

digraph g {
  s0 -> s0 [label=0];
  s0 -> s0 [label=1];
  s0 -> s1 [label=1];
  s1 -> s2 [label=0];
  s1 -> s2 [label=1];
  s2 -> s3 [label=0];
  s2 -> s3 [label=1];
}

Arătăm cum poate fi citit un astfel de graf pentru a-l prelucra; exemplul nu face decât să-l tipărească într-un format ușor diferit. În OCaml, funcția scanf folosește un format similar cu cel din C, dar nu primește adrese, ci o funcție care va primi valorile citite și le va prelucra în modul dorit.
De exemplu, pentru a aduna doi întregi, putem scrie

Scanf.scanf "%d %d" (fun x y -> x + y)

sau mai simplu

Scanf.scanf "%d %d" (+)

și putem tipări valoarea obținută:

print_int (Scanf.scanf "%d %d" (+))

Pentru ușurința scrierii, putem deschide un modul și folosi atunci direct numele funcțiilor lui, fără a fi necesar ca prefix numele modulului.

open Scanf        (* putem scrie scanf in loc de Scanf.scanf *)

Mai departe, funcția loop() (de argument unit) citește și tipăreăte o tranziție, în formatul indicat, și se reapelează. Citirea va eșua la sfârșit de fișier; această excepție este tratată în funcția exterioară printgraph() care apelează loop(); în acel moment nu a mai rămas nimic de făcut, indicat prin () .

În program, citim întâi antetul grafului și apoi apelăm funcția de citire și tipărire.

Programul poate fi compilat în format bytecode cu comanda ocamlc program.ml și apoi se poate rula cu redirectarea intrării, ./a.out < fisier.dot ceea ce va cauza intrarea să fie citită din fișier.

let printgraph() =
  let rec loop() =                (* scanf mai are ca parametru o functie *)
    scanf " %s -> %s [label=%c];" (fun s1 s2 c -> (* care ia valorile citite *)
      printf "%s -%c-> %s\n" s1 c s2);        (* si face ceva cu ele *)
    loop()                        (* apoi incercam sa citim mai departe *)
  in try loop() with Scan_failure _ | End_of_file -> ()        (* pana va esua la EOF *)

let _ = scanf "digraph %s {" (printf "Graph name: %s\n"); printgraph()

Probleme propuse

1. Completați programul de mai jos pentru a construi un automat finit nedeterminist citit de la tastatură.

module CM = Map.Make(Char)
module SM = Map.Make(String)
module S = Set.Make(String)

open Scanf

let addtrans src dst sym map = ...

let readgraph () =        (* citeste graf adaugand succesiv tranzitii *)
  let rec loop map =
    (try let (s1, s2, c) = scanf " %s -> %s [label=%c];" 
           (fun s1 s2 c -> (s1, s2, c)) in
         fun () -> loop (addtrans s1 s2 c map))
  with Scan_failure _ | End_of_file -> fun () -> map) ()
  in loop SM.empty

let _ = scanf "digraph %_s {" (); readgraph()

Funcția de tranziție va fi memorată ca dicționar indexat după stări (modulul SM) și care la rândul lui conține dicționare indexate dupa caractere (modulul CM) care conțin mulțimea de stări în care se poate tranziționa.

Trebuie completată funcția addtrans care ia ca parametru dicționarul și cele trei elemente ale unei noi tranziții (starea sursă, destinație și simbolul) și care adaugă această tranziție.

2. Determinați mulțimea stărilor în care se poate afla un automat finit nedeterminist după ce a parcurs un șir de simboluri furnizat ca intrare.
Scrieți o funcție care ia ca parametru o stare inițială, funcția de tranziție, și cuvântul de intrare (ca listă de caractere) și returnează mulțimea stărilor ce pot fi atinse. Reprezentați stările ca șiruri de caractere (numele lor). Puteți adapta ca exemplu concret automatul de la curs (pentru tratarea comentariilor), sau folosi unul citit ca în problema anterioară.

3. Completați programul dat pentru a construi un automat finit determinist de la tastatură și a simula comportarea lui. Stările automatului sunt reprezentate prin îtregi, iar automatul e reprezentat printr-un tablou de dicționare pentru fiecare stare. Dicționarele sunt indexate după simboluri (caractere) și conțin starea destinație pentru tranziția pe acel simbol. Dacă intrarea pentru un simbol lipsește, se consideră că automatul rămâne în aceeași stare.

Completați funcția addsym care adaugă la dicționarul pentru o stare src o tranziție în starea dst pe simbolul sym. Verificați că o astfel de tranziție nu există încă și că starea destinație e validă (mai mică decât n).
Implementați în funcția addtrans o verificare că starea sursă e validă (mai mică decât n)
Scrieți o funcție care ia automatul construit (tabloul a și un cuvânt de intrare (ca listă de caractere) și returnează starea în care se ajunge în automat parcurgând cuvântul.

module M = Map.Make(Char)

open Scanf

let addtrans a n src dst sym =
  let addsym sym dst cmap = ...
  in a.(src) <- addsym sym dst a.(src)

let readgraph n =        (* citeste graf adaugand succesiv tranzitii *)
  let a = Array.make n M.empty in
  let rec loop () =
    scanf " %d -> %d [label=%c];" (fun n1 n2 c -> addtrans a n n1 n2 c);
    loop ()
  in try loop () with Scan_failure _ | End_of_file -> a

let g = scanf "digraph %_s { size=%u; " (fun n -> readgraph n)

Marius Minea

Last modified: Wed Nov 27 8:10:00 EET 2013