Semigrupos, Autómatos e Linguagens
Objetivos
Fornecer uma introdução básica à Teoria dos Semigrupos, efetuar um estudo elementar, matematicamente rigoroso, de alguns tópicos da Teoria da Computação, nomeadamente dos Autómatos Finitos e das Linguagens Regulares, e ainda estabelecer as pontes que interligam estas duas áreas do conhecimento.
Caracterização geral
Código
10833
Créditos
6.0
Professor responsável
António José Mesquita da Cunha Machado Malheiro
Horas
Semanais - 4
Totais - 56
Idioma de ensino
Inglês
Pré-requisitos
Conhecimentos de Álgebra.
Bibliografia
- 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.
Método de ensino
As aulas são teóricas/práticas participadas, com exposição oral dos conceitos e metodologias devidamente complementada com exemplos e resoluções de problemas bem como sessões hands on. Eventuais dúvidas poderão ser esclarecidas no decurso das aulas ou em sessões individuais marcadas com os professores.
A avaliação contínua é baseada em dois testes. Se um aluno não obtiver aprovação através de avaliação contínua poderá vir a obtê-la num exame de recurso.
Método de avaliação
1. AVALIAÇÃO CONTÍNUA
A avaliação contínua consiste na realização, durante o período letivo, de dois testes presenciais e/ou a distância na plataforma Moodle, sendo cada um deles cotado de 0 a 20 valores (com arredondamento a uma casa decimal).
Podem apresentar-se a qualquer teste todos os alunos que, à data do mesmo, se encontrem inscritos na Unidade Curricular.
2. APROVAÇÃO E CLASSIFICAÇÃO FINAL
Sejam T1 e T2 as classificações obtidas no 1º e 2º testes, respectivamente, arredondadas às décimas.
A classificação final, CF, do aluno é obtida pelo arredondamento às unidades de (0,5 × T1 + 0,5 × T2), excepto se a CF for superior a 17, caso em que o aluno poderá optar entre ficar com a classificação final de 17 ou realizar uma prova complementar para defesa de nota. A aprovação à UC ocorre sempre que CF ≥ 10. Se CF for inferior a 10 o aluno reprova.
3. EXAME
Podem apresentar-se a exame todos os alunos inscritos na UC.
A nota do exame (NE) substitui a nota dos testes para a obtenção da classificação final, CF. A classificação final, CF, do aluno é obtida pelo arredondamento às unidades de NE, excepto se a CF for superior a 17, caso em que o aluno poderá optar entre ficar com a classificação final de 17 ou realizar uma prova complementar para defesa de nota. A aprovação à UC ocorre sempre que CF ≥ 10. Se CF for inferior a 10 o aluno reprova.
4. MELHORIA DE NOTA
Todo o aluno que pretenda apresentar-se a melhoria de nota deve cumprir, para esse efeito, as formalidades legais de inscrição (informações na Repartição Académica). A classificação do exame de melhoria é obtida de acordo com o indicado em 4. Se este resultado for superior ao já obtido anteriormente na disciplina, será tomado como nota final. Caso contrário, não se verifica melhoria de nota.
Conteúdo
1. Generalidades
2. Relações de Green
3. Semigrupos regulares, incluindo semigrupos 0-simples e a teorema de Rees-Suschkewitsch
4. Semigrupos inversos: uma breve introdução
5. Linguagens. Linguagens Racionais e Autómatos Finitos
6. Gramáticas: uma breve introdução. Gramáticas Regulares
7. Monóide de Transições e Monóide Sintáctico
8. Pseudovariedades de semigrupos e de variedades de linguagens racionais: uma breve introdução