Limbaje formale şi automate

Credite 6

Semestrul de toamnă

Titular de curs: Conferenţiar Constantin Ciubotaru, Biroul 330, Institutul de Matematică şi Informatică AŞM, E-mail: [email protected]

Eligibilitatea: MSc Informatica, MSc Matematică şi Informatică

Pre-rechezit: Studii universitare de licenţă (ciclul I) Matematică şi Informatică.

Structura: Curs teoretic – 30 ore (2 ore săptămânal)

                   Seminar - 30 ore (2 ore săptămânal)

                  Activităţi individuale ale studentului – 120 ore

Activităţi formative

Cursul special „Limbaje formale si automate” are drept scop prezentarea aspectelor teoretice şi practice ale limbajelor formale, automatelor şi aplicarea lor la proiectarea şi implementarea produselor program. Extinderea ariei de aplicabilitate a calculatoarelor, creşterea complexităţii şi intelectualizarea comunicării utilizatorului cu calculatorul necesită dezvoltarea unor metode adecvate pentru rezolvarea acestor probleme. Anume teoria limbajelor formale şi a automatelor oferă soluţii optimale pentru problemele ce ţin de elaborarea, formalizarea şi implementarea procesoarelor de text, limbajelor de programare, interfeţelor inteligente, sistemelor de gestiune a bazelor de date, aplicaţiilor Web. Cunoaşterea limbajelor formale şi a automatelor este benefică atât pentru orice profesionist în domeniul programării, cât şi pentru  cei  ce vor să se apropie de acest domeniu. Cunoaşterea noţiunilor şi algoritmilor de bază din teoria limbajelor formale şi a automatelor este absolut necesară pentru într-o lucrare scrisă sub formă de eseu.

Conţinutul cursului

INTRODUCERE.Noţiuni preliminare: vocabular, şir, limbaj. Metode de descriere a limbajelor. Gramatici generative. Gramatici şi limbaje formale, clasificarea Chomsky. 

LIMBAJE REGULATE ŞI AUTOMATE FINITE. Gramatici regulate şi automate finite. Definiţii, exemple.

Automate finite deterministe  (AFD) şi nedeterministe (AFND). Teorema de echivalenţă a AFD şi AFND.

Echivalenţa gramaticilor regulate şi a automatelor finite. Lema de pompare şi aplicaţiile ei. Minimizarea automatelor finite. Expresii regulate. Aplicarea limbajelor regulate la proiectarea şi implementarea analizoarelor lexicale.

GRAMATICI ŞI LIMBAJE INDEPENDENTE DE CONTEXT. AUTOMATE CU MEMORIE STIVĂ. Arbori de derivare, derivare dreaptă, derivare stângă. Teorema de ramificare. Transformări echivalente asupra gramaticilor independente de context, teorema substituţiilor. Eliminarea simbolurilor inaccesibile şi neproductive. Gramatici independente de context cu ε-producţii. Eliminarea redenumirilor. Forma normală Chomsky. Recursia stângă. Forma normală Greibach. Teorema “uvwxy” şi aplicaţiile ei. Automate cu memorie stivă: definiţii, exemple.

Echivalenţa gramaticilor independente de context şi a automatelor cu memorie stivă. Solvabilitatea analizei sintactice pentru limbajele independente de context. Algoritmul Cooke-Younger-Kassami. Complexitatea algoritmului.

Lista surselor bibliografice

Toader Jucan. Limbaje formale şi automate. MATRIX ROM, Bucureşti, 1999, 163 pp.; S. Marcus : Gramatici si automate finite, Editura Academiei, Bucuresti, 1964; I. Creanga, C. Reischer, D. Simovici : Introducere algebrica in informatica, vol II, Limbaje formale, Ed. Junimea, 1974; Gheorghe Grigoraş. Limbaje formale şi tehnici de compilare. Universitatea ”Al. I. Cuza'',  Iaşi, 1985; Adrian Atanasiu. Bazele informaticii.- Universitatea Bucureşti, 1987; Adrian Atanasiu, Alexandru Mateescu. Limbaje formale. Culegere de probleme. Universitatea Bucureşti, 1990; Axo A., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. т.1,2.  Москва, Мир, 1978; J. E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Second Edition. Addison Wesley, 2001, 521 pp.

J. Hopcroft, J. Ulman: Formal Languages and their Relations to Automata, Adison Wesley Publ. Comp., 1969; L. Livovschi, N. Tandareanu, s.a. Bazele informaticii, Ed. did. ped. 1981.

Evaluarea

Activitatea studentului va fi monitorizată la fiecare tip de activitate. La sfârşitul cursului va avea loc examenul final (180 min., scris), care va include un test complex de exerciţii la nivel de cunoaştere, integrare şi aplicare a cunoştinţelor. Nota finală se va constitui din testarea continuă pe parcursul semestrului (5%), rezultatele activităţii la seminare (45%), lucrări practice (10%) şi examenul final (40%).