1. Lista caracterelor unui șir
Scrieți o funcție care ia ca parametru un șir de caractere și returnează lista caracterelor din șir. Dacă s e un șir, puteți scrie s.[i] pentru caracterul de indice i (începând de la 0) din șirul s. Deci "salut".[1] este 'a'.
Încercați să scrieți funcția crescând indicele și acumulând o listă, până când indicele ajunge la lungimea șirului și încercarea de acces la s.[i] generează excepția Invalid_argument "index out of bounds". Returnați atunci lista.
Funcția va fi utilă pentru a putea furniza un șir ca intrare la un automat sau expresie regulată, transformându-l întâi în listă de caractere.
2. Definiți un automat care acceptă toate șirurile de 0 și 1 care nu au trei caractere identice consecutive.
Indicatie: Automatul va avea stări care corespund ultimelor două caractere întâlnite.
Scrieți funcția de tranziție, definiți stările acceptoare, și scrieți în final o funcție care ia ca parametru un șir și returnează dacă e acceptat sau nu.
Definiți preferabil automatul și funcțiile în program. Dacă nu, desenați-l pe hârtie. În ambele cazuri explicați soluția.
3. Demonstrați că expresiile regulate (1+0)*1*
și (1|10)* sunt echivalente, adică reprezintă același limbaj. Am notat cu | reuniunea (alternativa) și cu e+ repetiția lui e cel puțin o dată.
Pentru soluție, construiți automatele (minimizate) corespunzătoare celor două expresii și verificați că sunt la fel. Alternativ, demonstraț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 bucăți corespunzătoare expresiei de sub *.