Linguagens formais

linguagens formaisAutômatos Finitos
Linguagens Formais Rodrigo Alves Costa [e-mail] Teoria dos Autômatos
• Lida com definições e propriedades de modelos matemáticos de computação. • É constituído basicamente de dois modelos:
– Autômato finito: utilizado em processadores de texto, compiladores, e projetos de hardware. – Gramática livre-de-contexto: utilizado em linguagens de programação e inteligência artificial.

Autômatos Finitos
• Bons modelos computacionais para quantidades pequenas de memória. • O que se pode fazer com uma memória tão pequena?
– Muitas coisas úteis – na verdade, 98% dos dispositivos computacionais são desta natureza. – Microcontroladores, microprocessadores... Todos usam a chamada máquina de estados finita para controlar seus estados.

1

Autômatos Finitos
• Exemplo de dispositivo: controle de uma porta automática Porta
Tapete Frontal Tapete Posterior

Frente Atrás Ambos Nenhum Frente Atrás Ambos

Fechado

Aberto

Nenhum

Autômatos Finitos: controlador para uma porta automática
Sinal de entrada Estado Fechado Aberto Nenhum Fechado Fechado Frente Aberto Aberto Atrás Aberto Aberto Ambos Fechado Aberto

Esse controlador é um computador com apenas 1 bit de memória, memó capaz de registrar em quais dos dois estados o controlador está. está

Autômatos Finitos
• Ao começar a descrever a teoria matemática de autômatos finitos, fazemos isso no nível abstrato, sem referência a qualquer aplicação específica. • A seguir, vamos ver alguns exemplos usando um diagrama de estados, e identificar conceitos de estado inicial, estado de aceitação e transição

2

Autômatos Finitos
•
– –

Uma máquina M1 que:
Recebe cadeias de bits como entrada Aceita somente aquelas que começam com um ou mais zeros seguidos de um ou mais 1’s apenas.
0 q0 1 1 0 q2 q1 0,1

Exemplo: 1101 1. Começa no estado q0. 2. Lê 1, segue a transição de q0 para q1. 3. Lê 1, segue a transição de q1 para q1. 4. Lê 0, segue a transição de