Automata and formal languages
A.Y. 2017/2018
Learning objectives
Nel corso si espongono in modo concettuale problematiche classiche (analisi e sintesi) relative a Sistemi e Modelli, abituando lo studente all'uso di metodi formali.
Expected learning outcomes
Undefined
Lesson period: Second semester (In case of multiple editions, please check the period, as it may vary)
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Course syllabus and organization
Linea Milano
Responsible
Lesson period
Second semester
ATTENDING STUDENTS
Course syllabus
NON-ATTENDING STUDENTS
Basic notions.
Word monoids, languages, language operations, recognition and generative systems for languages. Recursive and recursively enumerable languages. Grammars and derivations. Regular, context-free, context-sensitive grammars and related classes of languages.
Regular languages.
Deterministic and non deterministic finite state automata. Regular grammars and finite state automata. Regular expressions. Kleene's Theorem. Syntactic congruences and constructions of minimal automata. Applications: regular expressions in Unix.
Context-free languages.
Derivation trees. Ambiguous grammar and languages. Chomsky normal form. Pumping lemma for context-free languages. Greibach normal form. Pushdown automata. Context-free languages and pushdown automata. Applications: XML.
Word monoids, languages, language operations, recognition and generative systems for languages. Recursive and recursively enumerable languages. Grammars and derivations. Regular, context-free, context-sensitive grammars and related classes of languages.
Regular languages.
Deterministic and non deterministic finite state automata. Regular grammars and finite state automata. Regular expressions. Kleene's Theorem. Syntactic congruences and constructions of minimal automata. Applications: regular expressions in Unix.
Context-free languages.
Derivation trees. Ambiguous grammar and languages. Chomsky normal form. Pumping lemma for context-free languages. Greibach normal form. Pushdown automata. Context-free languages and pushdown automata. Applications: XML.
Course syllabus
Basic notions.
Word monoids, languages, language operations, recognition and generative systems for languages. Recursive and recursively enumerable languages. Grammars and derivations. Regular, context-free, context-sensitive grammars and related classes of languages.
Regular languages.
Deterministic and non deterministic finite state automata. Regular grammars and finite state automata. Regular expressions. Kleene's Theorem. Syntactic congruences and constructions of minimal automata. Applications: regular expressions in Unix.
Context-free languages.
Derivation trees. Ambiguous grammar and languages. Chomsky normal form. Pumping lemma for context-free languages. Greibach normal form. Pushdown automata. Context-free languages and pushdown automata. Applications: XML.
Word monoids, languages, language operations, recognition and generative systems for languages. Recursive and recursively enumerable languages. Grammars and derivations. Regular, context-free, context-sensitive grammars and related classes of languages.
Regular languages.
Deterministic and non deterministic finite state automata. Regular grammars and finite state automata. Regular expressions. Kleene's Theorem. Syntactic congruences and constructions of minimal automata. Applications: regular expressions in Unix.
Context-free languages.
Derivation trees. Ambiguous grammar and languages. Chomsky normal form. Pumping lemma for context-free languages. Greibach normal form. Pushdown automata. Context-free languages and pushdown automata. Applications: XML.
Professor(s)