Last modified in: October 3, 2010 18:23

 

 

 

 

 

Formal Languages and Automata Theory ( Limbaje formale si teoria automatelor )

Curs obligatoriu, anul II , sem IV , 2c+ 1 s+1l / saptamâna , Nr. credite: 7 , Specializarea: Matematica-informatica

1. Obiectivele cursului: Familiarizarea studentilor cu lucrul cu sirurile de caractere, studiul proprietatilor si a modurilor de generare, descrierea unor masini care modeleaza situatii reale si care accepta siruri de caractere

2. Continutul de baza: Semigrupuri si monoizi (definitii, exemple; morfisme; substructuri, substructuri generate; relatia nucleara a unui morfism; structuri factor (cât); teorema de izomorfism; produse (semi)directe).  Limbaje si semigrupuri (alfabet, limbaj definitii, exemple; concatenarea cuvintelor; semigrup (monoid liber); proprietatea de universalitate; proprietati). Limbaje (operatii cu limbaje; proprietati; limbaje regulate si limbaje rationale, relatii de echivalenta asociate unui limbaj si legaturile dintre ele) Semiautomate (modele care conduc la considerarea notiunii; definitie; tabelul si graful de tranzitie; Exemple; completatul unui semiautomat; extinderea functiei de tranzitie; semigrupul unui semiautomat; morfisme; semiautomat factor. Automate Mealy (Definitie; mod de lucru; conectarea automatelor (serie si paralel); Graful de tranzitie; Exemple; Retele neuronale modelare cu ajutorul masinilor Mealy). Masini Turing (definitii; modele de masini Turing; masina Turing universala). Gramatici (Exemplu de generare; definitie formala; relatiile de derivare, limbaj generat). Clase de limbaje (Ierarhia lui Chomsky; proprietati la închidere pentru L 3. Automate finite : definitie, proprietati; limbaj acceptat si clasa L A ; automat minimal, legatura cu limbajele regulete. Automate pushdown: definitii, proprietati; limbaj acceptat. Alte modele de calcul intalnite in literatura de specialitate. Comentarii de final.

Note de curs

3 . Sistemul de evaluare al studentului: examen si forma de evaluare: 50% lucrare scrisa si 50% evaluarea pe parcursul semestrului

4. Tematica lucrarilor de laborator si de seminar: Aplicatii practice la problematica prezentata la curs

5. Discipline care trebuie parcurse în prealabil:

- obligatorii: Algebra I , Logica si teoria multimilor

6. Bibliografie curs:

CAZANESCU , V. E., Introducere în teoria limbajelor formale , Ed. Academiei, Bucuresti, 1983.

CREANGA , I., REISCHER, C., SIMOVICI, D., Introducere algebrica în informatica. Teoria automatelor , Ed. Junimea, Iasi, 1973.

CREANGA , I., SIMOVICI, D., Teoria algebrica a semigrupurilor cu aplicatii , Ed. Tehnica, Bucuresti, 1977.

GRIGORAS , G., Limbaje formale si tehnici de compilare , Ed. Universitatii "Al. I. Cuza", Iasi, 1985.

JUCAN , T., Limbaje formale si automate , Ed. Matrix Rom, Bucuresti, 1999

7. Bibliografie seminar si laborator:

JUCAN , T., ANDREI, S., Limbaje formale si teoria  automatelor , Universitatii "Al. I. Cuza", Iasi, 2001.