AUTOMATA, LANGUAGES AND COMPLEXITY

Clelia DE FELICE AUTOMATA, LANGUAGES AND COMPLEXITY

0522500004
DIPARTIMENTO DI INFORMATICA
EQF7
COMPUTER SCIENCE
2020/2021



YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2016
PRIMO SEMESTRE
CFUHOURSACTIVITY
1AUTOMI, LINGUAGGI E COMPLESSITÀ
324LESSONS
2AUTOMI, LINGUAGGI E COMPLESSITÀ
324LESSONS
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 CATALOG PROBLEMS FROM THE POINT OF VIEW OF THE RESOURCES (SPACE AND TIME) REQUIRED FOR THEIR SOLUTION.
•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. REDUCIBILITY.

THE CHOMSKY HIERARCHY.

TIME COMPLEXITY AND SPACE COMPLEXITY.

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. 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 AND OPERATIONAL 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-05-23]