Bazele teoriei calculului - limbaje formale si automate

Cartea de fata urmareste o expunere clara si accesibila a rezultatelor din domeniu si mai ales familiarizarea studentilor cu abordarea matematica a unor probleme legate de structurile de date, teoria compilatoarelor si dezvoltarea deprinderii de a folosi notiuni abstracte si metoda matematica de demonstratie in aceste domenii.

Cuprins:

1. Limbaje formale  

1. 1. Notiuni introductive. Exemple de limbaje

1. 2. Generarea unui limbaj. Generarea limbajelor cu sisteme de rescriere (Sisteme semi Thue)              

1. 3. Gramatici       

1. 4. Exemple

1. 5. Operatii cu limbaje      

1. 6. Ierarhia Chomsky        

1. 7. Proprietati de inchidere ale familiilor de limbaje     

1. 8. Nota bibliografica

 

2. Limbaje regulate si automate finite     

2. 1. Automate deterministe cu numar finit de stari       

2. 1. 1. Reprezentarea automatului finit  printr-o diagrama de tranzitie

2. 2. Automate finite nedeterministe

2. 3. Legatura dintre automatele finite si gramaticile regulate      

 

3. Expresii regulate

3. 1. Definitia recursiva pentru expresii regulate            

3. 2. Echivalenta dintre automatele finite nedeterministe si expresiile regulate

3. 3. Constructia unui automat finit nedeterminist cu l-tranzitii pentru o expresie regulata

3. 4. Ecuatii si sisteme de ecuatii pentru definirea limbajelor regulate        

3. 5. Ecuatii in retele            

3. 5. Clase de limbaje definite prin ecuatii        

3. 6. Relatii elementare pentru rezolvarea sistemelor liniare          

3. 7. Nota bibliografica

 

4. Proprietatile limbajelor regulate     

4. 1. Lema de pompare        

4. 2. Teorema  Myhill-Nerode            

4. 3. Minimizarea automatelor finite  

4. 4. Proprietati de inchidere pentru limbaje regulate     

4. 5. Probleme de decizie pentru limbaje regulate           

4. 6. Algoritmi de decizie    

4. 7. Probleme       

 

5. Gramatici independente de context si automate push-down

5. 1. Automate push-down

5. 2. Automatul push-down nedeterminist      

5. 3. Legatura automatelor push-down cu limbajele independente de context

5. 4. Limbaje independente de context             

5. 5. Arbori de derivare       

5. 6. Simplificarea gramaticilor independente de context              

5. 7. Forma normala Chomsky           

5. 8. Forma normala Greibach            

5. 9. Nota bibliografica

 

6. Proprietatile limbajelor independente de context

6. 1. Lema de pompare pentru limbajele independente de context              

6. 2. Algoritmi de decizie pentru limbaje independente de context             

6. 3. Probleme de apartenenta           

 

7. Masini turing, calculabilitate

7. 1. Introducere  

7. 2. Modelul de baza al masinii Turing           

7. 3. Reprezentarea masinilor Turing prin diagrame       

7. 4. Tehnici evoluate de constructie a masinilor Turing              

7. 4. 1. Stocarea informatiilor in controlul finit 

7. 4. 2. Banda de intrare cu mai multe piste      

7. 4. 3. Marcarea simbolurilor             

7. 4. 4. Dilatarea sau condensarea cuvantului de intrare

7. 4. 5. Subrutine   

7. 5. Modificari ale masinii Turing    

7. 5. 1. Masina Turing cu banda infinita in ambele sensuri           

7. 5. 2. Masina Turing cu mai multe benzi        

7. 5. 3. Masina Turing nedeterminista

7. 5. 4. Masina Turing bidimensionala

7. 5. 5. Masina Turing cu mai multe capete de citire si inregistrare              

7. 6. Functii calculabile       

7. 7. Relatia dintre gramaticile de tip 0 si masinile Turing             

7. 8. Nota bibliografica

 

8. Masinile turing si inteligenta artificiala       

8. 1. Problema completitudinii sistemelor formale          

8. 2. Problema opririi pentru masini Turing     

8. 2. 1. Masina Turing Universala

8. 2. 2. Nerezolvabilitatea problemei opririi       

8. 3. Decidabilitate si Nedecidabilitate             

8. 3. 1. Limbaje recursive si recursiv numarabile             

8. 3. 2. Problema de corespondenta a lui Post 

8. 3. 3. Versiunea modificata a problemei de corespondenta Post

8. 3. 4. Nedecidabilitatea problemei de corespondenta a lui Post 

8. 4. Masinile Turing si activitatea creierului  

8. 5. Nota bibliografica

8. 6. Probleme recapitulative              

 

9. Limbaje lindenmayer        

9. 1. Introducere  

9. 2. Sisteme de dezvoltare si limbaje de tip L 

9. 3. Relatii intre limbajele de tip L si limbajele generative            

9. 4. Operatii cu limbaje 0L 

9. 5. Functii de crestere

9. 6. Nota bibliografica

 

10. Notiuni introductive de teoria multimilor 

10. 1. Relatii intre multimi   

10. 2. Operatii cu multimi    

10. 3. Paradoxurile teoriei multimilor 

10. 4. Latice si algebre Boole             

10. 5. Alte operatii cu multimi

 

11. Relatii      

11. 1. Definitia relatiilor       

11. 2. Proprietatile relatiilor

11. 3. Partitia unei multimi  

11. 4. Relatii de ordine        

11. 5. Produsul relatiilor      

11. 6. Aplicatii      

11. 7. Produsul aplicatiilor  

 

12. In loc de incheiere

Alonzo Church (1903 - 1995)            

Kurt Gödel (1906 - 1978)    

Alan Turing (1912 - 1954) 

Stephen Cole Kleene (1909 - 1994)  

Noam Chomsky (1928 - )   

Aristid Lindenmayer (1925 - 1989)   

Solomon Marcus (1925 - ) 

Seymour Ginsburg (1928 - 2004)      

Sheila Greibach (1939 - )    

John Hopcroft (1939 - )     

Nr. de pagini: 176
Anul aparitiei: 2007