Automate finite, expresii regulate și gramatici

Automate finite

Simulator și conversie pentru automate și expresii regulate.

A1. Comentarii C Completați automatul dat în program (redat și mai jos) 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 stări *)

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

let rec fold_input state =    (* ca fold_left, pe șirul caracterelor citite *)
  try let c = input_char stdin in        (* încearcă să citească un caracter c *)
      fold_input (delta state c)        (* aplică din nou pe starea următoare *)
  with _ -> state                   (* excepție la citire: returnează starea curentă *)

(* starea acceptoare e Out: programul se termină afară din comentariu *)
let _ = print_endline (if fold_input 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_input 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 funcția delta pe o valoare-acumulator state și caracterul citit de la intrare c, continuând cu delta state c ca acumulator (starea următoare). Ea reprezintă funcția de tranziție δ^* pentru șiruri de caractere (citite de la intrare).
Mai jos un program echivalent în C:

#include <stdio.h>

typedef enum { OUT, SLASH, IN } state_t;
char *name[] = { "out", "slash", "in" };

state_t delta(state_t state, int c)	// funcția de tranziție
{
  switch(state) {	// doar pentru comentariile cu //
  default:	// nu va ajunge aici, sunt doar 3 valori posibile
  case OUT: return c == '/' ? SLASH : OUT;
  case SLASH: return c == '/' ? IN : OUT;
  case IN: return c == '\n' ? OUT : IN;
  }
}

int main(void)  // comentariu până la sfârșit de linie
{
  state_t state = OUT;
  for (int c; (c = getchar()) != EOF; )
    state = delta(state, c);
  printf("end state: %s\n", name[state]);
}

Compilați programul din terminal cu comanda ocamlc comment1.ml, respectiv gcc comment1.c.
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 .

A2. Automate și traductoare Modificați funcția de tranziție de mai sus 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 și ca matrice, indexată după stare și simbol de intrare.

Expresii regulate

regex101: expresii regulate online. Echivalență de expresii regulate.

R1. Exemple comune Scrieți expresii regulate și/sau automate pentru următoarele noțiuni:

numere întregi în baza 10, cu semn opțional
numere reale în baza 10, în notația din C: semn, parte întreagă, punct, parte fracțională, exponent (E/e urmat de număr cu semn). Orice parte e opțională, dar trebuie să existe parte întreagă sau fracționară. Dacă lipsește punctul, trebuie să existe exponent (altfel, numărul e considerat întreg).
adresă de e-mail (considerați un subset cu caractere obișnuit intâlnite)

Pentru problemele următoare, 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ă.

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

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

R4. 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ă.

R5. Expresia acceptă șirul? Pentru a determina pas cu pas dacă un șir poate fi generat de o anumită expresie regulată, adaptăm testul pentru primul caracter de la problema 3.
Determinăm expresia regulată care reprezintă toate continuările posibile după primul simbol a în expresia re dată. Aceasta se numește derivata expresiei regulate re în raport cu simbolul a.
Altfel spus, deriv(re, a) e expresia regulată reprezentând toate șirurile w astfel încât șirul aw e generat de expresia inițială.
Apelați apoi repetat funcția pentru a determina dacă o expresie regulată acceptă un șir dat. Folosiți liste de caractere sau modulul String pentru lucrul cu șiruri.

Marius Minea

Last modified: Mon Dec 4 10:20:00 EET 2017