Semigroups, Automata and Languages
Objectives
Provide a basic introduction to the Theory of Semigroups, make an elementary study, mathematically rigorous, of some topics of the Theory of Computation, in particular of Finite Automata and Regular Languages, and also providing the bridges that connect these two areas of knowledge.
General characterization
Code
10833
Credits
6.0
Responsible teacher
António José Mesquita da Cunha Machado Malheiro
Hours
Weekly - 4
Total - 56
Teaching language
Inglês
Prerequisites
Knowledge of Algebra.
Bibliography
- J.M. Howie, Automata and Languages, Oxford, 1991.
- J.M. Howie, Fundamentals of semigroup theory, Oxford, 1995.
- J.E. Pin, Varieties of formal languages, Plenum, 1986.
- M.V. Lawson, Finite Automata, Chapman & Hall/CRC, 2003.
- GAP - Groups, Algorithms, and Programming, 2008.
Teaching method
Classes are theoretical/practical with oral presentation of concepts, methodologies, and examples,
complemented with problem-solving. Specific student difficulties will be addressed during classes or in individual sessions scheduled with the professor. Continuous assessment is based on two tests. If a student does not obtain approval through continuous assessment he can try it in an additional assessment.
Evaluation method
1. CONTINUOUS EVALUATION
The continuous evaluation consists of carrying out, during the academic period, two in-person and/or distance tests on the Moodle platform, each one quoted from 0 to 20 values (rounded to one decimal place).
All students who, at the time of the test, are enrolled in the Curricular Unit can take any test.
2. APPROVAL AND FINAL CLASSIFICATION
Let T1 and T2 be the classifications obtained in the 1st and 2nd tests, respectively, rounded to decimals.
The student''s final grade, CF, is obtained by rounding up to the units of (0.5 × T1 + 0.5 × T2), except if the CF is greater than 17, in which case the student may choose to keep the final grade of 17 or take a complementary test for grade defense. Approval to the UC occurs whenever CF ≥ 10. If CF is below 10 the student fails.
3. EXAM
All students enrolled in the UC can take the exam - see point 1.
In this case, the exam grade (NE) replaces the test''s grade to obtain the final grade, CF. The final grade, CF, of the student, is obtained by rounding to the units of NE, except if the CF is greater than 17, in which case the student may choose to keep the final grade of 17 or take a complementary test for grade defense. Approval to the UC occurs whenever CF ≥ 10. If CF is below 10 the student fails.
4. GRADE IMPROVEMENT
All students wishing to present themselves with a grade improvement must comply with the legal registration formalities for this purpose (information at the Academic Services). The classification of the improvement exam is obtained as indicated in 4. If this result is higher than the one previously obtained in the course, it will be taken as the final grade. Otherwise, there is no improvement in the final grade.
Subject matter
1. Basics
2. Green''s Relations
3. Regular semigroups, including 0-simple semigroups and the Rees-Suschkewitsch Theorem
4. Inverse Semigroups: an introduction
5. Languages. Rational languages and finite automata
6. Grammars: a brief introduction. Regular grammars
7. Transition monoid and syntactic monoid
8. Pseudovarieties of semigroups and varieties of rational languages: a brief introduction