Linguagens Formais e Autômatos

Apresentação do Plano de Ensino

Linguagens Formais e Autômatos

� LFA� Código - CMP4145� Turma – C01� Engenharia da’Computação e Ciência da

Computação� Horário:

� Terça e Sexta: 20:30 – 22:00 � Sábado: 9:00 – 10:30

Comunicação

� Utilizaremos e-mail� Enviar msn:

� Whatsapp

Plano de Ensino

� Ementa� Objetivos Gerais� Objetivos Específicos� Conteúdo Programático� Metodologia� Avaliação

Plano de Ensino

� Atividade Externa à Disciplina� Bibliografia Básica� Bibliografia Complementar� Cronograma

� Disponível no SOL

Ementa

� Alfabetos, palavras, linguagens e gramáticas.� Linguagens regulares e autômatos finitos. � Linguagens livres de contexto e autômatos

com pilhas. � Linguagens sensíveis ao contexto. � Linguagens com sentido de frase. � Máquinas de Turing como reconhecedores

de linguagens.

Objetivos Gerais

� Dominar os conceitos de linguagens formais� Dominar os conceitos de máquinas de

estados e autômatos finitos� Dominar os conceitos de gramáticas

Objetivos Específicos

� Construir autômatos finitos� Entender e elaborar gramáticas� Reconhecer linguagens.

Conteúdo Programático

� Introdução e Conceitos Básicos� Conjuntos e relações;� Provas formais;� Alfabetos, cadeia de caracteres, linguagens e

gramáticas.

Conteúdo Programático

� Linguagens Regulares� Autômato Finito Determinístico;� Autômato Finito Não Determinístico;� Conversão de autômatos� Expressão regular� Gramática regular� Propriedades das linguagens regulares� Conversão expressão regular – autômato finito

determinístico

Conteúdo Programático

� Linguagem Livre de Contexto� Gramática livre de contexto� Árvore de derivação� Simplificação da gramática� Autômato de Pilha

� Linguagens Recursivamente Enumeráveis e Sensíveis ao Contexto� Máquina de Turing

Metodologia

� Aulas expositivas;� Formação de grupos para definição,

discussão e solução de problemas;� Estudo dirigido- resolução de exercícios em

classe.� Metodologias Ativas

Avaliação

� NF = 0.4 * N1 + 0.6 * N2� N1 (0.0 – 10.0)

� (P1 + P2)

� PN2 (0.0 – 9.0)� (P3 + P4 + AI)

Avaliação InterdisciplinarAI

� Valor: 0 a 1.0� Somada na N2 de todas as disciplinas� Calendário: 9 de Novembro

Freqüência

� Falta Reprova� Mínimo: 75%� 120 presenças; 30 faltas� Cada aula conta 2 presenças� Cada AED conta 4 presenças

Atividade Externa à Disciplina

� AED 1: Projeto dos meus sonhos� Filmes: Jobs, Piratas do Vale do Silicio, Rede Social, O Jogo da

Imitação, Teoria de Tudo.� Entrega: 06/10/2017

� AED 2 – III Congresso de Ciência e Tecnologia� Entrega: 21 de outubro de 2017.

� AED 3 – II Jornada Cientifica da ECEC� Entrega: 28 de novembro de 2017.

� Só serão aceitas atividades entregues na data correta. � Cada AED somara 4 presenças.

Bibliografia Básica

Bibliografia Complementar

Bibliografia Complementar

Material de Apoio

Cronograma

Breve Histórico

� Em 1936, Alan Turing (matemático) propôs a possibilidade de se construir um computador digital através da formalização de um procedimento em tempo finito.

Breve Histórico

� Turing estabeleceu um modelo formal de algoritmo.

� Ele reduziu os vários sistemas formais a um sistema básico, tornando possível o computador digital.

Breve Histórico

� Sistema Formal� Um “jogo” rigorosamente definido. � Especificar:

� Regras para manipulação dos símbolos.� A natureza dos símbolos.� A situação inicial � Lista de movimentos permitidos a uma dada

posição.

Breve Histórico

� Alan Turing criou uma máquina que executava operações sobre a teoria dos números por meio de regras de um sistema formal embutidas na mesma.

Breve Histórico

� Isso gerou uma nova perspectiva para formalizar a matemática.

� Turing descobriu que os números são mais importantes como símbolos.

Breve Histórico

� Tese de Church

“qualquer procedimento pode ser descrito por uma máquina de Turing”

Breve Histórico

� A teoria das linguagens formais surgiu nas décadas de 1940 e 1950.

� Seu objetivo inicial era modelar a função do cérebro, desenvolvendo teorias relacionadas com as linguagens naturais.

Breve Histórico

� Em 1969, S. Cookestendeu o estudo de Turing do que podia e do que não podia ser calculado.

� Classe de Problemas� P, NP, NP-hard

Porque estudar LFA?

� Apresenta uma fundamentação matemática da computação (fornece provas).

� É pré-requisito essencial para a disciplina de compiladores

Porque estudar LFA?

� Dá suporte à verificação da computabilidadede problemas (problemas reais tem solução computacional).

Porque estudar LFA?

� Para entender a complexidade de um problema. Um problema pode ser fácil ou difícil de se resolver. A complexidade de algoritmos pode fazer esta classificação baseando-se na dificuldade computacional do problema.

Porque estudar LFA?

� Para entender a teoria computacional. Alguns problemas básicos não podem ser resolvidos. Ela classifica os problemas em solúveis e não solúveis