Aula 3 - Automatos e Linguagens Formais

Prévia do material em texto

�PAGE �
�PAGE �1�
Autômatos e Linguagens Formais – Aula 3
Operações com cadeias (strings ou palavras de uma Linguagem)
Intersecção de A com B
A ( B = {x/x ( A e x ( B}
União de A com B
A ( B = {x/x ( A ou x ( B}
Diferença de A e B
A - B = {x/x ( A e x ( B}
Concatenação
AB = {xy /x ( A e y ( B}
Exemplo: {a,ab}{b,ba} = {ab, aba, abb, abba}. Normalmente, AB ( BA. 
Reconhecedores e Geradores de linguagens - Como definir/representar uma linguagem?
Uma linguagem finita pode ser definida através da enumeração das sentenças constituintes ou através de uma descrição algébrica.
Uma linguagem infinita deve ser definida através de representação finita. 
Reconhecedores ou sistemas geradores são dois tipos de representações finitas. 
Um reconhecedor é um dispositivo formal usado para verificar se uma determinada sentença pertence ou não à linguagem. São exemplos de reconhecedores autômatos finitos, autômatos de pilha e máquinas de Turing. 
Um sistema gerador é um dispositivo formal usado para gerar de forma sistemática as sentenças de uma dada linguagem. São exemplos de sistemas geradores as gramáticas. Todo reconhecedor e todo sistema gerador pode ser representado por um algoritmo.
Exercício 
	Leia a Bibliografia dada a seguir e procure por:
Operações com cadeias (ou strings ou palavras de uma linguagem)
Definições de Reconhecedores e Geradores 
Bibliografia:
BLAUTH Paulo. Linguagens Formais e Autômatos. Série Livros Didáticos, Sagra Luzzato Editores, Porto Alegre, 2002.
HOPCROFT, J.E., Ullman, J.D., Motwani, R., Introdução a Teoria dos Autômatos, Linguatens e Computação, Rio de Janeiro, Editora Campus, 2002.
HOPCROFT, J.E., Ullman, J.D., Motwani, R., Introduction to Automata Theory, Languagens, and Computation, New York, Addison Wesley, 2001 
GALLI, HAREL, DAVID. Algoritmics, the spirit of computing, Addison Wesley, Worringhan, 1987. 
LEWIS/PAPADIMITRIOU. Elements of the theory of computation. Prentice-Hall, 1981.