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 pot fi incluse în constante caracter și ghilimelele în constante șir sau caracter dacă sunt precedate de backslash \ .
În nicicare din cele trei construcții sintactice (comentarii, constante caracter sau șir) nu se interpretează special caracterele care încep una din celelalte construcții.

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.

Probleme propuse

1. Comentarii Completați automatul dat cu stări și tranziții astfel încât să urmărească ambele tipuri de comentarii din C.

type state = In | Out | Slash

let delta = function        (* function: state -> char -> state *)
  | In -> (function
             | '\n' -> Out
             | _ -> In)
  | Out -> (function
             | '/' -> Slash
             | _ -> Out)
  | Slash -> (function
               | '/' -> In
               | _ -> Out)

let fold_in f =                (* fold f on a character stream with initial value v *)
  let rec fold1 v =        (* that is, compute f (f (f (v c1) c2) c3 ...*)
    (try let c = input_char stdin in
        fun () -> fold1 (f v c)
     with _ -> fun () -> v) ()
  in fold1

let _ = prerr_endline (if fold_in delta Out = Out then "OK" else "ends in comment")

Funcția de tranziție a automatului e delta. Funcția fold_in e similară cu List.fold_left dar pe o secvență de caractere citite de la intrare (până la sfârșitul acesteia). Ea apelează repetat o funcție f pe o valoare-acumulator v și caracterul citit de la intrare c, continuând cu f v c ca acumulator. O folosim pentru a implementa funcția de tranziție pentru șiruri de caractere δ^* pornind de la delta.
Compilați programul din terminal cu comanda ocamlc fisier.ml. Apoi rulați programul cu ./a.out. După ce ați introdus caracterele dorite, tastați Ctrl-D pentru a semnala încheierea intrării (Ctrl-Z sub Windows). Pentru a prelua textul dintr-un fișier (prin redirectarea intrării) dați comanda ./a.out fisier .

2. Automate și traductoare Modificați funcția de tranziție de la pct. 1 astfel încât automatul să scrie la ieșire tot textul în afara comentariilor.
Funcția delta va returna mai departe aceleași valori; tipărirea se face înainte de a preciza valoarea returnată, folosind secvențierea cu ; a evaluării expresiilor.

3. Citirea automatelor. Citim de la intrare un automat scris în formatul dot pentru grafuri. Automatul e descris ca graf orientat: o muchie reprezintă o tranziție dintr-o stare în altă stare, etichetată 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];
}

Programul de mai jos implementează, asemănător cu problema 1, o funcție care citește repetat triplete formate din două șiruri (nume de stări) și un caracter (simbolul de intrare pentru tranziție), și aplică repetat o funcție f pe o valoare acumulator și tripletele citite.

open Scanf
let fold_in3 f =        (* aplica f repetat pe acumulator si cele 3 elemente citite *)
  let rec fold3 acc =
    (try let (s1, s2, c) = scanf " %s -> %s [label=%c];" 
           (fun s1 s2 c -> (s1, s2, c)) in
         fun () -> fold3 (f acc s1 s2 c)
     with Scan_failure _ | End_of_file -> fun () -> acc) ()
  in fold3

let printgraph = fold_in3 (fun () -> Printf.printf "%s -> %s [%c]\n")
                          
let _ = scanf "digraph %_s {" (); printgraph()

În funcția printgraph, tripletul (stare, stare, simbol) e doar tipărit. Modificați programul în așa fel încât să construiască un dicționar (de la stare și intrare la stare) care să reprezinte funcția de tranziție a automatului determinist.

4.Tranziții implicite Dacă alfabetul e mare (de exemplu, întregul set de caractere la programul de filtrat comentarii), e anevoios să specificăm explicit sute de tranziții. Putem implementa atunci funcția de tranziție ca un dicționar care pentru fiecare stare conține o pereche: un dicționar de la simboluri la stări, și o stare următoare implicită pentru fiecare simbol necuprins în dicționar.

5 Intersecția și reuniunea Pentru două automate finite peste aceeași mulțime de simboluri, cu funcțiile de tranziție reprezentate ca dicționar, și având deasemenea stările (inițiale, acceptoare, și în totalitate), construiți automatul care reprezintă intersecția, respectiv reuniunea.

Marius Minea

Last modified: Mon Nov 24 23:30:00 EET 2014