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")

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

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 *)

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