Introdução às Linguagens e aos Autômatos de Estados Finitos

Autômatos, Linguagens e Computação

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

  • Definir formalmente linguagem.
  • Compreender a relação entre linguagem e problema computacional.
  • Definir formalmente o conceito de autômatos de estados finitos.

Conceitos Fundamentais

  • Alfabeto : Conjunto finito de símbolos (ex.: ).
  • Cadeia : Sequência finita de símbolos.
  • Fecho de Kleene de um alfabeto , denotado , é o conjunto de tadas as cadeias sobre .
    • , onde .
  • Fecho Positivo de um alfabeto , denotado , é o conjunto de todas as cadeias não vazias sobre .

Linguagem

Uma Linguagem sobre um alfabeto é um subconjunto de

  • Conjunto de cadeias sobre .
  • Exemplo: sobre
  • Note que linguagens podem ser infinitas, mas alfabetos precisam ser finitos.

Linguagem e Problema

Um problema pode ser visto como um conjunto de instâncias que requerem uma resposta "sim" ou "não".

  • Focaremos na pergunta: Dados e , ?
  • Problema de decisão: Cabe decidir se a cadeia pertence à linguagem .
  • Dessa forma, qualquer problema computacional pode ser expresso por linguagens:
    • úé
      • Ou seja, linguagem dos números primos.
      • Ou seja, linguagem dos números pares em representação binária.

Mais exemplos de linguagens na lousa

Breve Histórico

Ano Contribuição Autor(es)
1929 Formalização de máquinas abstratas A. M. Turing (máquina de Turing)
1936 Autômatos finitos simples S. C. Kleene (expressões regulares)
1945 Autômato determinístico e não‑determinístico M. Rabin & S. Scott
1960s Linguagens formais na computação Aho, Ullman, Hopcroft

Sistema de Estados Finitos

  • Modelo (matemático) computacional simples
  • Estrutura abstrata que descreve a execução de algoritmos e dispositivos computacionais através de estados discretos e transições.
  • Cada estado representa uma configuração completa do sistema em um instante; transições são acionadas por símbolos de entrada (ou eventos) que modificam a configuração.
    • Entrada: cadeia
    • Saída: pertence ou não pertence (i.e., uma decisão)
  • Modelam desde circuitos digitais simples até protocolos de comunicação, linguagens formais e processos de controle industrial.

Autômatos Finitos Determinísticos (AFD)

Processadores de cadeias
Reconhecedor de linguagens
Aceita ou Rejeita uma cadeia
Detecção de padrões
Processa um símbolo por vez

Exemplo 1: Diagrama de Estados

center

Diagrama de estados para um AFD simples. Fonte: Wikipedia.

Autômato Finito Determinístico (AFD)

Definição formal: Um AFD é uma -upla , onde:

  • é um conjunto finito de estados.
  • é um conjunto finito de símbolos (alfabeto).
  • é uma função de transição determinística entre estados.
  • é o estado inicial.
  • é o conjunto finito de estados finais (de aceite).
  • Determinismo: Para cada símbolo do alfabeto existe apenas um estado possível para o qual o autômato pode transitar a partir do (único) estado atual.

Exemplo 1: Formalização

  • , onde:
  • Estados: , inicial.
  • Alfabeto: .
  • Função :
  • Estado final: .
  • Pergunta 1: Qual a propriedade das cadeias aceitas por ?
  • Pergunta 2: Qual a forma tabular de ?
  • Pergunta 3: Qual aplicação prática de ?

center

Exemplo de AFD simples. Fonte: Wikipedia.

Exemplo 2

, onde:

  • Estados: , inicial.
  • Alfabeto: .
  • Função :
  • Estado final: .
  • reconhece (uma linguagem de) cadeias com número ímpar de zeros.

Representação gráfica do AFD na lousa

Exercício Prático

  • Dado o AFD abaixo que aceita apenas números binários múltiplos de 3:
    • Descreva formalmente .
    • Especifique em formato tabular a função de transição .

center

Fonte: Wikipedia.

Conceitos Chave

Termo Definição Observação
Estado Ponto de posição da máquina. Finito, discretos.
Transição Movimento entre estados. Determinística vs não‑determinística.
Estado Inicial Onde a computação começa. Único.
Estado Final (Aceitante) Reconhecimento bem‑sucedido. Pode haver zero ou mais.
Palavra/Entrada Sequência de símbolos em . A máquina aceita se terminar em

Exercícios Práticos

Construa AFDs que reconheça as linguagens:

  1. Paridade de 1: éú
  2. Padrão final fixo: .
  3. Reconhecimento de subcadeia: .

Resumo e Próximos Passos

  • Definição Formal:
    • Começa em .
    • Para cada símbolo da palavra, segue .
    • Palavra aceita se o último estado é um estado final (pertence a ).
  • Determinismo: para qualquer , existe exatamente um destino.
  • Decidibilidade: aceitação pode ser testada em tempo linear na extensão da palavra.
  • Aplicações Práticas: Análise lexical em compiladores (identificação de tokens). Reconhecimento de padrões em sistemas embarcados e protocolos de comunicação.

center

Atividade recomendada: Leitura do capítulo 1 e das seções 2.1 e 2.2 do capítulo 2.

Perguntas e Discussão

  1. Quais técnicas podem ser usadas para identificar e corrigir erros em um AFD construído manualmente?
  2. Como o tamanho do conjunto de estados afeta a eficiência da execução? Em que situações um AFD com mais estados pode ser desejável apesar de maior custo de memória?
  3. Quais são as limitações intrínsecas dos AFDs na modelagem de sistemas complexos? Cite exemplos onde o modelo determinístico não consegue capturar a dinâmica do problema.
  4. Como podemos otimizar um AFD já construído sem alterar sua linguagem reconhecida?
  5. Qual é o impacto da cardinalidade do alfabeto na complexidade de transição de um AFD? Exemplo: Alfabeto binário versus alfabeto de caracteres ASCII completo.

- Compreender o conceito de linguagem regular

* Diferenciar autômato determinístico (AFD) e não‑determinístico (NFA). * Apresentar técnicas básicas de construção, simplificação e equivalência. * Relacionar AEF a linguagens regulares e a expressões regulares.

| | | **Estado** | Ponto de atenção no autômato; pode ser inicial, final ou intermediário.|

* A **finitude** dos estados garante propriedades de decidibilidade: podemos verificar se uma palavra pertence à linguagem reconhecida, determinar ciclos, otimizar recursos e provar correções por análise formal.