Expresii regulate

Temă pentru laborator

1. Scrieți o expresie regulată pentru toate șirurile de 0 și 1 care nu au trei simboluri consecutive de 1. (Ajutați-vă de exemplul de la curs, al șirurilor care nu conțin doi de 1 consecutivi).

2. Construiți un automat finit pentru același limbaj.

3. Obțineți expresia regulată pornind de la automatul finit.

4.* (opțional) Câte cuvinte de n simboluri 0 și 1 există care nu conțin k de 1 consecutivi ?

Probleme propuse

Pentru a testa problemele aveți definită o funcție de citire a unei expresii regulate (folosind notația | pentru reuniunea/alternativa limbajelor)

1. Scrieți o funcție care ia ca parametru o expresie regulată (cu tipul din exemplul de mai sus) și o tipărește în formatul uzual (cu *, + și paranteze). Se presupune că simbolurile sunt caractere tipăribile, diferite de cele speciale amintite.

2. Scrieți o funcție care returnează mulțimea tuturor caracterelor cu care ar putea începe o expresie regulată dată.
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). Scrieți o funcție auxiliară care determină dacă o expresie regulată poate genera șirul vid.

3. Similar cu problema dinainte, determinați simbolurile care pot fi ultimele într-o expresie regulată dată.

4. Asemănător cu problema 2, determinați derivata unei expresii regulate re în raport cu un simbol a. Aceasta e definită care expresia regulată care reprezintă toate sufixele șirurilor care încep cu a din expresia regulată inițială. Altfel spus, deriv(re, a) e expresia regulată reprezentând toate șirurile s astfel încât as e generat de expresia inițială. Puteți aplica funcția repetat pentru a determina dacă un șir poate fi generat de o expresie regulată.


Marius Minea
Last modified: Mon Dec 1 14:30:00 EET 2014