Expresii regulate și automate

Automate finite

1. 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.

2. Șiruri și ghilimele Similar cu tema, definiți funcția de tranziție pentru un automat care știe să recunoască un program cu șiruri de caractere scrise corect:

• Un șir de caractere (posibil vid) are ghilimele " la început și la sfârșit
• Dacă vrem să apară caracterul ghilimele în șir, punem \ înaintea lui
• Dacă vrem să apară caracterul \ în șir, îl dublăm: \\
• Caracterul \ urmat de orice altceva constituie eroare (stare din care nu se mai iese).

3. Construiți automatul Pornind de la o listă de tranziții date sub forma de triplete (stare,intrare,stare) rezolvați următoarele probleme.
Stările sunt reprezentate ca întregi, intrările sunt caractere. Deci lista [(0, '1', 1); (0, '0', 0); (1, '0', 0)] reprezintă automatul de la p.24 din curs (fără a indica însă starea inițială și cele acceptoare).
a) Formați mulțimea stărilor din care pornesc tranziții și mulțimea stărilor în care se termină tranziții. Identificați dacă sunt stări din care nu pornesc sau în care nu ajung tranziții
b) Construiți alfabetul automatului (presupunând că nu conține și caractere care nu apar în listă).
c) Construiți relația de tranziție sub formă de dicționar cu chei (stare, intrare) și valori mulțimi de stări. Semnalați o excepție dacă pentru aceeași stare și intrare lista nu indică două stări rezultante diferite.
Pentru chei scrieți modulul

module IntChar = struct
 type t = int * char
 let compare = compare
end

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

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

5. 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.

6. Ultimul 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ă.

7. Derivata expresiei regulate Dată fiind o expresie regulată și un simbol (caracter) din alfabet, ne punem problema care sunt toate șirurile reprezentate de expresie care încep cu simbolul dat. Se poate arăta că ele pot fi descrise tot de o expresie regulată, numită derivata expresiei inițiale în raport cu simbolul dat.
Scrieți o funcție care calculează această expresie. Cazurile interesante sunt concatenarea (dacă prima expresie poate genera șirul vid) și închiderea Kleene.