Linguagens e Autômatos Finitos Determinísticos

Autômatos, Linguagens e Computação

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

• Definir formalmente o conceito de linguagem.
• Compreender a relação entre linguagem e problema computacional.
• Definir formalmente o conceito de autômatos finitos determinísticos (AFDs).
• Compreender o processo de reconhecimento de cadeias através de AFDs.

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.

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.

Exemplo 1: Diagrama de Estados

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

Prática: Processar as cadeias e

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. Ou seja, .
• é 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

Reconhecimento de linguagem

Definição (Linguagem de uma Máquina): Seja o conjunto de todas as cadeias aceitas por , dizemos que é a linguagem aceita por , ou seja, .

• Um autômato reconhece apenas uma linguagem. Ou seja, a linguagem é única.
  • Pode ser a linguagem vazia .
• Pode reconhecer infinitas cadeias.

Observação importante sobre AFDs

Condições de parada: após processar o último símbolo de uma cadeia ,

• Aceita a cadeia : se o AFD assume estado de aceitação;
• Rejeita a cadeia : se o AFD não assume estado de aceitação ou não está definida para alguma transição .
• Sempre para. Sem loop infinito.

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 .

Fonte: Wikipedia.

Função de Transição Estendida

Definição formal: Dado um AFD , a função de transição estendida , definida como

para, e

• Definição recursiva.
• é o estado de após processar toda a cadeia a partir do estado .
• Permite descrever o estado final após leitura de uma cadeia completa sem repetir explicitamente cada transição.
• Aceite: Um AFD aceita se , caso contrário, rejeita .

Função de Transição Estendida para

Exemplo de AFD simples. Fonte: Wikipedia.

Linguagem de um AFD

A linguagem de um AFD , denotada por , é definida como

Se é a linguagem para algum AFD , então dizemos que
é uma linguagem regular.

Conceitos Chave

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

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.