Teoria da Comput., Autômatos e Linguagens Formais

Codigo	Carga Horária
	T	E	L/P	CHT
CIC206	2	2	0	80

Ementa

Fundamento de linguagem formal. Hierarquia de Chomsky. Autômato finito determinísticos (AFD). Autômato finito não-determinísticos (AFN). Transformação de AFN para AFD. Linguagem livre de contexto e autômato de pilha. Linguagem sensível ao contexto. Máquina de Turing. Computabilidade, decidibilidade e redutibilidade.

Descrição

A disciplina Teoria da Computação, Autômatos e Linguagens Formais abrange a teoria, técnicas e ferramentas que permitirão ao egresso resolver problemas computacionais específicos associados a autômatos e linguagens, bem como entender o conceito de computabilidade. Os elementos das teorias a serem estudadas nesta disciplina podem ser encontrados diariamente em aplicações tais como expressões regulares, linguagens de programação e compiladores, apenas para citar alguns. Além disso, esta disciplina possui relacionamentos com outras disciplinas do currículo, em especial com Matemática Discreta e depois com Compiladores, oferecendo, assim, uma oportunidade de integrar os conhecimentos aprendidos aqui com os conhecimentos aprendidos nessas outras disciplinas.

Responsável

Docentes

Bibliografia

Complementar

• HOPCROFT, John E. Formal languages and their relation to automata. Reading, Mass: Addison-Wesley, 1969. 242 p.