Logică și structuri discrete - Exerciții cu automate și expresii regulate

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.


Marius Minea
Last modified: Tue Nov 28 16:15:00 EET 2017