Linguagens formais

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (563 palavras )
  • Download(s) : 0
  • Publicado : 26 de outubro de 2012
Ler documento completo
Amostra do texto
linguagens formaisAutômatos Finitos
Linguagens Formais Rodrigo Alves Costa
rodrigo.costa@gmail.com

Teoria dos Autômatos
• Lida com definições e propriedades de modelos matemáticos decomputaçã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 deprogramaçã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

NenhumAutô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ômatosfinitos, 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 estadoinicial, 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 umou 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...
tracking img