View
10
Download
0
Category
Preview:
Citation preview
Teoria de Linguagens Formais e Autômatos
Prof. Juan Moises Mauricio Villanueva
jmauricio@cear.ufpb.br
www.cear.ufpb.br
1
• Usando para expressar formalmente uma linguagem computacional
• Abordagem teórica de Sintaxe e Semântica
Sintaxe: Checagem de instruções de programa
Semântica: Erros de programas em lógicas (mais complicados de serem identificados)
2
1. Linguagens Formais
1. Linguagens Formais
• Um símbolo designado por é uma entidade.
• Letras e dígitos são exemplos típicos de símbolos
• A partir de um conjunto de símbolos, é possível definir um alfabeto.
• Definição de Alfabeto
Alfabeto é um conjunto não vazio de símbolos, representado por
={, , } é um alfabeto formado pelos símbolos , , .
A combinação dos símbolos de um alfabeto é denominado palavra.
3
1. Linguagens Formais
• Definição de Palavra
A palavra sobre o alfabeto é qualquer combinação de um número finito de símbolos (com ou sem repetição) de , na forma:
4
0,1 010101 ; 1010111
, , ,..., ;
Alfabetos Palavras
a b c z automatica abc
Palavras com os símbolos dos alfabetos
1. Linguagens Formais
• Definição de Comprimento de uma Palavra
O comprimento de uma palavra s, representada por |s|, é igual ao número de símbolos que a compõem.
5
0,1 010101 010101 6
, , ,..., 10
Alfabetos Palavras Comprimento
a b c z automatica automatica
1. Linguagens Formais
6
0
1
2
{ }
{ , }
{ , , , }
1. Linguagens Formais
• Concatenação de palavras
Dada duas palavras s1 e s2 sobre um alfabeto , com
s1=12...k
s2=k+1k+2...n
A concatenação de s1 e s2, definido por s1s2 é dada por:
s1 s2 =12...kk+1k+2...n
7
1. Linguagens Formais
8
1 2 3
1
* 0 1 2 3
0
...
.. { }
k
k
k
k
1. Linguagens Formais
9
1. Linguagens Formais
10
1. Linguagens Formais
11
*{ : ^ }
Por tanto :
L u v uv L
L L
1. Linguagens Formais
• Tipos de Formalismos
Reconhecedores: recebe uma palavra e retorna um valor para indicar se é ou não da linguagem
Geradores: define um conjunto de regras que podem ser combinadas para gerar palavras
12
1. Linguagens Formais
• Classificação das Linguagens
13
Linguagens Enumeráveis Recursivamente (Tipo 0)
Linguagens Sensíveis ao Contexto (Tipo 1)
Linguagens Livres do Contexto (Tipo 2)
Linguagens Regulares (Tipo 3)
2. Linguagens Regulares
14
2. Linguagens Regulares
• Formalismo Reconhecedor
Recebe uma palavra de entrada contida em uma linguagem
Dada uma linguagem deve-se indicas se a palavra é aceita ou rejeitada
15
2. Linguagens Regulares
16
palavra nula .
3. Autômatos
Um autômato é um modelo matemático de máquinas, com entradas e saídas discretas, que reconhece um conjunto de palavras sobre um dado alfabeto.
Um autômato pode ser finito ou infinito e determinístico ou não determinístico.
17
3. Autômatos
Um autômato FINITO consiste de um conjunto finito de estados definido por X, e um conjunto de transições de estados definido por f, que ocorrem a partir de símbolos de entrada escolhidos sobre um alfabeto .
O estado inicial do autômato definido por x0 é o estado que se encontra antes de ler o primeiro símbolo.
Alguns estados do autômato são definidos como estados finais ou marcados Xm.
18
3. Autômatos
Um autômato reconhece exatamente as palavras para ser processadas que o levam a um estado marcado.
Caso o autômato que possua infinitos estados é definido como Autômato Infinito.
Se para cada símbolo de entrada existe exatamente uma transição de saída de cada estado, então o autômato é DETERMINISTICO.
Se existem duas ou mais transições de saída de um estado que podem ocorrer a partir do mesmo símbolo, então o autônomo é definido como NÃO DETERMINISTICO.
19
3. Autômatos
Um Autômato Finito Determinístico (AFD) é uma Quíntupla:
A=(X, , f, x0, Xm)
Em que:
X é o conjunto finito de estados do autômato x
é o alfabeto ou conjunto de símbolos
f: XX é a função de transição de estados
x0 X é o estado inicial
XmX é o conjunto de estados marcados
20
Permanecendo em um estado e lendo um símbolo do alfabeto faz o autômato
passar para outro estado ou mesmo ficar no mesmo
estado.
3. Autômatos
Um Autômato Finito Determinístico (AFD) pode ser representado por meio de um diagrama similar a máquinas de estados finitos
21
Estado Inicial
Estado Final
Estado restantes
s2 s1 Transição de 1 para 2, devido ao eve to a
f(a)
A tem 3 estados q1, q2, q3
A inicia no estado q1
O AFD recebe os símbolos de estada de maneira sequencial (um por um)
Após a leitura de cada símbolo, o AFD se movimenta de um estado para outro, de acordo com as regras da transição.
Quando o AFD lê o último símbolo retorna uma saída
Quando o AFD chega ao estado FINAL reconhece a palavra
Se não estiver no estado final não reconhece a palavra
Exemplo : AFD
22
q2 q1 q3
0
1
1 0
0,1
Exemplo : AFD
23
q2 q1 q3
0
1
1 0
0,1
Para uma entrada 1101
• Inicia no estado q1
• Lê 1, segue transição de q1 para q2
• Lê 1, segue transição de q2 para q2
• Lê 0, segue transição de q2 para q3
• Lê 1, segue transição de q3 para q2
• A entrada finalizou em um estado marcado, por tanto reconhece a palavra
3. Autômatos
Graficamente, um autômato é representado por um GRAFO DIRECIONADO cujos vértices representam os estados e cujos arcos representam a função de transição.
Os estados marcados são representados por vértices com linhas duplas.
O estado inicial é identificado por uma seta.
Conhecida a função de transição e o estado atual de um autômato, é possível determinar seu estado após processar um dado símbolo.
24
3. Autômatos
EXEMPLO: Dado um autômato AFD:
A=(X, , f, x0, Xm)
={a,b} (Símbolos)
X={1,2,3} (Estados)
f(a,1)=3 f(b,1)=2 f(a,2)=3
f(b,2)=1 f(a,3)=3 f(b,3)=2
x0=1 (Estado inicial)
Xm={3} (Estado marcado)
25
Transições de estados
3. Autômatos
A=(X, , f, x0, Xm)
={a,b}
X={1,2,3}
f(a,1)=3 f(b,1)=2
f(a,2)=3 f(b,2)=1
f(a,3)=3 f(b,3)=2
x0=1
Xm={3}
26
1
2 3
b
a
a
b
b
a
3. Simulação do Autômato
27
AFD=Autômato Finito Determinístico AFN=Autômato Finito Não Determinístico
3. Simulação do Autômato
A=(X, , f, x0, Xm)
={a,b}
X={1,2,3}
f(a,1)=3 f(b,1)=2
f(a,2)=3 f(b,2)=1
f(a,3)=3 f(b,3)=2
x0=1
Xm={3}
28
3. Simulação do Autômato
A=(X, , f, x0, Xm)
={a,b}
X={1,2,3}
f(a,1)=3 f(b,1)=2
f(a,2)=3 f(b,2)=1
f(a,3)=3 f(b,3)=2
x0=1
Xm={3}
29
3. Simulação do Autômato
A=(X, , f, x0, Xm)
={a,b}
P1 = aaba
A palavra P1 é valida já que é reconhecida pelo autômato.
30 Estado Marcado
3. Simulação do Autômato
O autômato reconhece uma determinada linguagem através da leitura sequencial de símbolos, mudando de estado a cada leitura.
A palavra é dita reconhecida se o estado alcançado após a leitura do último símbolo da palavra pertence ao conjunto de estados finais (marcados).
Cada símbolo lido atualiza o estado do autômato de acordo com uma função de transição.
31
3. Simulação do Autômato
A=(X, , f, x0, Xm)
={a,b}
P2 = aabb
A palavra P2 não é reconhecida pelo autômato porque o resultado das transições não leva a um estado marcado
32
3. Autômatos
33
Exemplo: Sistema de Manufatura
34
• Considere que em um sistema há um local de armazenamento de materiais a serem reciclados (la), inicialmente com sua capacidade completa de 02 itens.
• Há um robô (rb) que transporta as peças desse local para uma máquina que processa peça (mp).
• Esse mesmo robô (rb) transporta a peça trabalhada na máquina para um local de consumo (lc). Assim, sempre que uma peça é processada, ela é transportada para o local de consumo (lc).
Exemplo: Sistema de Manufatura
35
36
Estados discretos Um estado representa a situação atual
Estado Marcado
Símbolos (eventos)
37
• O alfabeto para este exemplo é dado pelo símbolos a, b ,c ,d:
a: símbolo que representa o evento rb pega peça
b: símbolo que representa o evento rb solta peça
c: símbolo que representa o evento mp processa peça
d: símbolo que representa o evento peça p o ta , isto é, peça já reciclada e pronta para ser consumida.
Eventos discretos São resultados das ações que ocorrem no sistema. Essas ações podem ser intencionais, de ocorrência espontânea controlada ou com a verificação de uma condição, e geralmente produzem mudanças de estado em intervalos de tempo aleatórios. Exemplos: Intencionais: Pressionar um Botão, abrir uma porta; Ocorrência espontânea: Falha na rede de comunicação,
Subtensão elétrica na rede de distribuição; Verificação de uma condição: temperatura fora da faixa. A
temperatura do reservatório, excede o limite da segurança.
38
a: sí olo ue ep ese ta o eve to rb pega peça : sí olo ue ep ese ta o eve to rb solta peça : sí olo ue ep ese ta o eve to mp p o essa peça
d: sí olo ue ep ese ta o eve to peça p o ta , isto é, peça já reciclada e pronta para ser consumida.
Recommended