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