Aula 2 - Automatos e Linguagens Formais

Prévia do material em texto

�PAGE �
�PAGE �3�
Autômatos e Linguagens Formais – Aula 2
Introdução à Teoria de Linguagens: Alfabetos, Cadeias de símbolos
Os estudos sobre linguagens formais iniciaram-se na década de 50 com o objetivo de definir matematicamente as estruturas das linguagens naturais. No entanto, verificou-se que a teoria desenvolvida aplicava-se ao estudo das linguagens de programação.
A teoria de linguagens formais engloba, basicamente, o estudo das características, propriedades e aplicações das linguagens formais, bem com a forma de representação da estrutura (sintaxe) e determinação do significado (semântica) das sentenças das linguagens. A importância desta teoria é dupla: tanto apóia outros aspectos teóricos da teoria da computação, tais como decibilidade, computabilidade, complexidade, etc., como fundamenta diversas aplicações computacionais como, por exemplo, processamento de linguagens, reconhecimento de padrões, modelagem de sistemas, etc. 
O que é uma linguagem?
• uma linguagem é uma forma de comunicação, usada por sujeitos de uma determinada comunidade;
• uma linguagem é o conjunto de SÍMBOLOS e REGRAS para combinar esses símbolos em sentenças sintaticamente corretas.
• uma linguagem é formal quando pode ser representada através de um sistema com sustentação matemática.
Assim sendo, são necessários conceitos matemáticos para o estudo das linguagens formais.
• Símbolo
Um símbolo é uma entidade abstrata básica sem definição formal. São exemplos de símbolos as letras, os dígitos, etc. Símbolos são ordenáveis lexicograficamente e, portanto, podem ser comparados quanto à igualdade ou precedência. Por exemplo, tomando as letras dos alfabetos, tem-se a ordenação A < B < C < ... < Z. A principal utilidade dos símbolos está na possibilidade de usá-los como elementos atômicos em definições de linguagens.
• Sentença (ou palavra)
Uma sentença (ou palavra) é uma seqüência finita de símbolos. Sejam P, R, I, M, e A símbolos, então PRIMA é uma sentença. As sentenças vazias, representadas por e, é uma sentença constituída por nenhum símbolo.
• Tamanho de uma sentença
O tamanho (ou comprimento) de uma sentença w, denotado por |w|, é dado pelo número de símbolos que compõem w. Assim, o tamanho da sentença PRIMA é 5 e o tamanho da sentença vazia é 0.
Alfabeto
Um alfabeto, denotado por V, é um conjunto finito de símbolos. Assim, considerando os símbolos dígitos, letras, etc., têm-se os seguintes alfabetos Vbinário = {0, 1}; Vvogais = {a, e, i, o, u}. É importante observar que um conjunto vazio também pode ser considerado um alfabeto.
O fechamento reflexivo de um alfabeto V, denotado por V*, é o conjunto infinito de todas as sentenças que podem ser formadas com os símbolos de V, inclusive a sentença vazia. O fechamento transitivo de um alfabeto V, denotado por V+, é dado por V* - {}. Seja V o alfabeto dos dígitos binários, V = {0, 1}. O fechamento transitivo de V é V+ = {0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}, enquanto que o fechamento reflexivo de V é V* = {, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}.
Linguagens e suas Representações
Uma linguagem formal L é um conjunto de sentenças formadas por símbolos tomados de algum alfabeto V. Isto é, uma linguagem sobre o alfabeto V é um subconjunto de V* (L 
Uma linguagem pode ser:
• finita: quando é composta por um conjunto finito de sentenças. Seja V = {a, b} um alfabeto, L1, L2 e L3 linguagens definidas conforme segue:
L1 = {w | w V* e |w| < 3}, ou seja, L1 é uma linguagem constituída por todas as sentenças de tamanho menor que 3 formadas por símbolos de V. Portanto, L1 = {, a, b, aa, ab, ba, bb}
L2 =  .
L3 = {}
As linguagens L2 e L3 são diferentes.
• infinita: quando é composta por um conjunto infinito de sentenças. Seja V = {a, b} um alfabeto, L1, L2 e L3 linguagens definidas conforme segue:
L1 = {w | w V* e |w| é par }, ou seja, L1 é uma linguagem constituída por todas as sentenças de tamanho par formadas por símbolos de V. Portanto, L1 = {, aa, ab, ba, bb, aaaa, aaab, aaba, ...}
L2 = {w | w é uma palíndrome}. Portanto L2 = {, a, b, aa, bb, aba, baab, ...}
L3 = linguagem de programação JAVA, ou seja, o conjunto infinito de programas escritos na linguagem de programação em questão.
Exercício 
	Leia a Bibliografia dada a seguir e procure por:
Definições de Alfabeto, String, cadeias
Operações com cadeias 
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.