1. Scrieți un automat care acceptă toate șirurile de a, b care conțin și un a și un subșir bb.
a) Construiți întâi câte un automat nedeterminist pentru fiecare din cele două condiții. Convertiți-l pe fiecare în automat determinist, și apoi faceți produsul celor două automate (intersecția limbajelor).
b) Construiți direct un automat nedeterminist pentru ambele condiții, și apoi convertiți-l în automat determinist.
2. Demonstrați că expresia regulată (0|10)* generează toate șirurile de 0 și 1 care nu se termină cu 1 și nu conțin doi 1 consecutivi. Folosiți inducția după lungimea șirurilor.
3. Demonstrați că expresiile regulate (0|01)* și (0+1)*0* sunt echivalente. Am notat cu | reuniunea (alternativa) și cu e+ repetiția lui e cel puțin o dată.
Arătați că orice șir acceptat de prima expresie e acceptat de a doua și reciproc, prin inducție după lungimea șirului, descompunând șirul în segmente corespunzătoare expresiei de sub *.
Alternativ, construiți automatele (minimizate) corespunzătoare celor două expresii și verificați că sunt la fel.