Clelia DE FELICE | AUTOMATA AND FORMAL LANGUAGES
Clelia DE FELICE AUTOMATA AND FORMAL LANGUAGES
cod. 0522500142
AUTOMATA AND FORMAL LANGUAGES
| 0522500142 | |
| COMPUTER SCIENCE | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2021/2022 |
| YEAR OF COURSE 1 | |
| YEAR OF DIDACTIC SYSTEM 2016 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | ||
|---|---|---|---|---|---|
| AUTOMI E LINGUAGGI FORMALI | |||||
| INF/01 | 3 | 24 | LESSONS | ||
| AUTOMI E LINGUAGGI FORMALI | |||||
| MAT/02 | 3 | 24 | LESSONS | ||
| Objectives | |
|---|---|
| KNOWLEDGE AND UNDERSTANDING. THE STUDENT MUST HAVE KNOWLEDGE OF COMPUTATIONAL MODELS AND GENERATING SYSTEMS. OF POTENTIALITY, LIMITATIONS, MATHEMATICAL ASPECTS AND AREAS OF APPLICATION OF THESE MODELS. APPLYING KNOWLEDGE AND UNDERSTANDING. THE STUDENT MUST BE ABLE •TO RECOGNIZE WHETHER A PROBLEM CAN BE SOLVED USING SOLUTIONS BASED ON ONE OF THE STUDIED COMPUTATIONAL MODELS. •TO STUDY OPEN RESEARCH PROBLEMS IN FORMAL LANGUAGES THEORY USING THE KNOWLEDGE ACQUIRED. |
| Prerequisites | |
|---|---|
| KNOWLEDGE OF DISCRETE MATHEMATICS, LOGIC, AND ALGORITHMS. DISCRETE MATHEMATICS: SETS, SET OPERATIONS, CARDINALITY, CARTESIAN PRODUCT, FUNCTIONS. LOGIC: PREDICATES AND QUANTIFIERS, PROOF METHODS AND STRATEGY. ALGORITHMS: ASYMPTOTIC NOTATION. |
| Contents | |
|---|---|
| DETERMINISTIC AND NONDETERMINISTIC FINITE AUTOMATA. REGULAR EXPRESSIONS AND LANGUAGES. DECISION PROBLEMS FOR REGULAR LANGUAGES. EQUIVALENCE AND MINIMIZATION OF AUTOMATA. REGULAR GRAMMARS. CONTEXT-FREE GRAMMARS AND LANGUAGES. PARSE TREES. PUSHDOWN AUTOMATA. DECISION PROBLEMS FOR CONTEXT-FREE LANGUAGES. TURING MACHINES. DECIDABILITY. THE CHOMSKY HIERARCHY. ELEMENTS OF THEORY OF CODES AND COMBINATORICS ON WORDS. |
| Teaching Methods | |
|---|---|
| CLASS LESSONS. THE LECTURES INCLUDE EXERCISES THAT WILL PRESENT EXAMPLES OF APPLICATIONS OF THOSE CONCEPTS, WITH THE AIM OF ENABLING THE STUDENT TO APPLY THE KNOWLEDGE ACQUIRED. |
| Verification of learning | |
|---|---|
| THE ASSESSMENT OF THE ACQUISITION OF THE BASIC CONCEPTS AND OF THE ABILITY TO APPLY THOSE CONCEPTS WILL BE IN AN ORAL EXAM. A PART OF THE ORAL TEST MAY BE SUBSTITUTED BY A SEMINAR OR A WRITTEN DISSERTION ON SCIENTIFIC ARTICLES RELATED TO ADVANCED TOPICS. THE EVALUATION CRITERIA INCLUDE THE COMPLETENESS AND CORRECTNESS OF THE LEARNING AND THE CLARITY OF THE PRESENTATION. THE MINIMUM GRADE (18) IS ASSIGNED WHEN THE STUDENT HAS A LIMITED KNOWLEDGE OF THE COMPUTATIONAL MODELS INTRODUCED AND SHOWS UNCERTAINTIES IN THE APPLICATION OF THE STUDIED METHODS. THE MAXIMUM GRADE (30) IS ASSIGNED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH UNDERSTANDING OF THE CONCEPTS AND METHODS STUDIED. IT IS ALSO ABLE TO SOLVE THE PROPOSED PROBLEMS AND SHOWS THE ABILITY TO LINK DIFFERENT CONCEPTS TOGETHER. ''LODE'' IS GIVEN WHEN THE CANDIDATE DEMONSTRATES SIGNIFICANT MASTERY OF THE THEORETICAL CONTENT AND SHOWS THAT SHE/HE IS ABLE TO PRESENT THE TOPICS WITH OWNERSHIP OF LANGUAGE AND AUTONOMOUS PROCESSING SKILLS. |
| Texts | |
|---|---|
| •M. SIPSER, INTRODUZIONE ALLA TEORIA DELLA COMPUTAZIONE, APOGEO, 2016 •J. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009. |
| More Information | |
|---|---|
| E-LEARNING PLATFORM WEB SITE: HTTP://ELEARNING.INFORMATICA.UNISA.IT/EL-PLATFORM/ CONTACT INFORMATION : CDEFELICE@UNISA.IT HTTPS://DOCENTI.UNISA.IT/001119/HOME |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-11-21]
