Automate finite, expresii regulate și gramatici

Automate finite

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

type state = In | Out | Slash  (* de completat cu alte stari *)

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

let fold_in f =         (* similar cu fold_left, dar pe sirul caracterelor citite din intrare *)
  let rec fold1 v =     (* calculeaza f (f (f (v c1) c2) c3 ... *)
    (try let c = input_char stdin in    (* incearca citirea unui nou caracter c *)
         fun () -> fold1 (f v c)        (* reusit: continua cu acumulatorul f v c *)
     with _ -> fun () -> v) ()          (* exceptie la sfarsit: returneaza acumulatorul *)
  in fold1

(* starea acceptoare e Out -- textul se termina afara din comentariu *)
  
let _ = print_endline (if fold_in delta Out = Out then "OK" else "ends in comment")
Starea inițială e Out (automatul nu a citit nimic, deci nu a început niciun comentariu). 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 (sub Windows: ./a). 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 .
Alternativ, puteți scrie un program C care face același lucru.

A2. Automate și traductoare Modificați funcția de tranziție de la temă 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.

A3. Simboluri consecutive Implementați în program (C sau ML) automatul de la temă (va recunoaște sau nu un șir citit de la intrare, până la linie nouă).
Dacă scrieți programul în C, puteți implementa funcția de tranziție direct ca matrice, indexată după stare și simbol de intrare.

Expresii regulate

Folosiți următorul tip pentru expresii regulate:
type regexp = Void | Eps | Sym of char
              | Alt of regexp * regexp (* alternativa, reuniune *)
              | Seq of regexp * regexp (* secventiere, concatenare *)
              | Rep of regexp        (* inchidere Kleene=repetitie *)
Aveți dat și un program care citește o expresie regulată, folosind notația | (nu +) pentru reuniune/alternativă.

R1. Șirul vid Scrieți o funcție care determină dacă o expresie regulată poate genera șirul vid.

R2. Primul caracter Scrieți o funcție care ia ca parametru o expresie regulată și returnează mulțimea tuturor caracterelor care pot fi primele într-un șir generat de acea expresie regulată.
Cazul cel mai interesant e al concatenării, când primul caracter poate proveni din prima expresie, sau din a doua, dacă prima expresie poate genera șirul vid (limbajul reprezentat de expresie conține limbajul vid). Folosiți pentru aceasta funcția de la punctul anterior.

R3. Ultimul caracter Scrieți o funcție care ia ca parametru o expresie regulată și returnează mulțimea tuturor caracterelor care pot fi ultimele într-un șir generat de acea expresie regulată.

Gramatici

G1. Litere mari și mici Fie următoarea gramatică: S ::= ε | ASa | BSb | ... | ZSz | .
Scrieți un program (în C sau ML) care determină dacă caracterele care apar în intrare (până la linie nouă) formează un șir generat de gramatică sau nu.

G2. Palindrom Fie următoarea gramatică: S ::= . | aSa | bSb | zSz .
Scrieți un program (în C sau ML) care determină dacă caracterele care apar în intrare (până la linie nouă) formează un șir generat de gramatică sau nu.

G3. Din prefix în postfix Scrieți o funcție care citește o expresie aritmetică în format prefix și o tipărește în format postfix. Puteți modifica funcția de la curs.

G4. Expresie postfix O expresie în formă postfix, de exemplu 3 2 + 5 4 - *, ceea ce înseamnă (3 + 2) * (5 - 4) poate fi descrisă de gramatica

Expr ::= număr Rest
Rest ::= ε | Expr op Rest
Scrieți o funcție care citește de la intrare o expresie în formă postfix cu operanzi întregi și returnează valoarea ei.


Marius Minea
Last modified: Wed Dec 7 18:00:00 EET 2016