Ausberto S. Castro Vera
Ciência da Computação
[email protected]
Linguagens Formais e Autômatos
São Paulo, Janeiro, 2011
c 2008-2011 por Ausberto S. Castro Vera. Todos os direitos reservados.
Copyright Nenhuma parte deste livro pode ser usada ou reproduzida por quaisquer meios sem
a permissão por escrito do autor
Autor
Ausberto S. Castro V., fez o bacharelado em Ciências Fı́sicas e Matemáticas na
Universidad Nacional de Trujillo (UNT), Perú, e tem o mestrado e doutorado em
Ciência da Computação pela Universidade Federal do Rio Grande do Sul (UFRGS),
Porto Alegre. Foi Professor a Tempo Integral na Universidad Nacional de Ingenierı́a (UNI), Lima, Professor Principal Experto na Universidad Nacional de Trujillo(UNT), Professor a tempo parcial da Universidad ”César Vallejo”, Trujillo, Professor a Tempo Integral na Universidade Regional Integrada do Alto Uruguai e
das Missões (URI), Campus de Frederico Westphalen, Professor do Curso de Mestrado em Modelagem Matemática da Universidade Regional do Noroeste do Estado
do Rio Grande do Sul (UNIJUI), Professor Visitante da Universidade Federal do
Rio Grande do Sul, na Coordenação do Programa de Mestrado Interinstitucional
URI-UFRGS em Matemática Aplicada,Professor a Dedicação Exclusiva do Centro
Universitário Adventista de São Paulo (UNASP). Atualmente é Professor a tempo
parcial da Universidade Nove de Julho (UNINOVE), Consultor integrante do BASis
(Avaliador Institucional e de Cursos) do INEP/MEC (Ministério da Educação) e
do Conselho Estadual de Educação de São Paulo (CEE-SP). Membro da Sociedade
Brasileira de Computação (SBC), Association for Computing Machinery (ACM) e
da IEEE Computer Society.
ii
Sumário
Sumário
v
1 Fundamentos Matemáticos
1
1.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.3
Representação Gráfica de Conjuntos . . . . . . . . . . . . . . . . . . .
3
1.4
Especificação de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . .
5
1.5
Conjuntos Especiais . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.6
Cardinalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7
Álgebra de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.1
Operações Básicas entre Conjuntos . . . . . . . . . . . . . . . 11
1.7.2
Álgebra de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . 13
1.8
Definições Recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9
Seqüências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.10 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.11 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.12 Indução Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.13 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.14 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.14.1 Propriedades e definições . . . . . . . . . . . . . . . . . . . . . 30
1.15 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2 Linguagens
2.1
33
Palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
iii
2.1.1
2.2
Operações com palavras . . . . . . . . . . . . . . . . . . . . . 36
Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.1
Especificação de Linguagens . . . . . . . . . . . . . . . . . . . 39
2.2.2
Operações sobre Linguagens . . . . . . . . . . . . . . . . . . . 40
2.3
Conjuntos Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4
Expressões Regulares
. . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5
Linguagens Regulares
. . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6
Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Autômatos Finitos
49
3.1
Uma ferramenta: JFLAP . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2
Autômatos Finitos Determinı́sticos . . . . . . . . . . . . . . . . . . . 52
3.3
Autômatos Finitos Não-Determinı́sticos . . . . . . . . . . . . . . . . . 59
3.4
Autômatos Finitos e Expressões Regulares . . . . . . . . . . . . . . . 61
3.5
Transições Lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.6
Equivalência de autômatos . . . . . . . . . . . . . . . . . . . . . . . . 63
3.7
Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4 Gramáticas Livre de Contexto
69
4.1
Gramáticas e Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2
Exemplos de Gramáticas e Linguagens . . . . . . . . . . . . . . . . . 74
4.3
Tipos de Gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4
Gramáticas e Linguagens Regulares . . . . . . . . . . . . . . . . . . . 76
4.5
Gramáticas Regulares e Autômatos . . . . . . . . . . . . . . . . . . . 78
4.6
Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Autômatos de Pilha
5.1
83
Autômatos de Pilha e Linguagens . . . . . . . . . . . . . . . . . . . . 83
5.1.1
Funcionamento de un Autômato de Pilha . . . . . . . . . . . . 85
5.2
Variações de um Autômato de Pilha . . . . . . . . . . . . . . . . . . . 89
5.3
Autômatos de Pilha e Linguagens Livre de Contexto . . . . . . . . . 90
iv
v
5.3.1
Construção de gramáticas livres de contexto a partir de autômatos
de pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4
Formas Normais de Chomsky e Greibach . . . . . . . . . . . . . . . . 93
5.5
Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6 Máquinas de Turing
97
6.1
Decidibilidade, Computabilidade e Computadores . . . . . . . . . . . 97
6.2
Máquina de Turing Padrão . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2.1
Funcionamento da Máquina de Turing . . . . . . . . . . . . . 100
6.3
Máquina de Turing como Aceitantes de Linguagens . . . . . . . . . . 102
6.4
Critérios de Aceitação alternativos . . . . . . . . . . . . . . . . . . . 104
Referências Bibliográficas
104
Capı́tulo 1
Fundamentos Matemáticos
1.1
Introdução
Neste capı́tulo apresentamos un conjunto de fundamentos matemáticos básicos e
necessários para entender as Linguagens Formais e os Autômatos. Assumimos que
o leitor está familiarizado com a Teoria dos Conjuntos, relações e funções. Neste
texto são apresentados apenas as definições e exemplos, de maneira muito superficial,
porém, formal. Um bom pré-requisito para esta matéria é a disciplina de Matemática
Discreta.
1.2
Conjuntos
Definição 1.1 Conjunto
Conjunto é uma coleção bem definida de zero ou mais objetos distintos, que possuem
uma propriedade comum.
Da definição devemos destacar três aspectos:
• A coleção de objetos: deve ser bem definida, isto é, sem ambigüidades, dúvidas,
incertezas. Coleções bem definidas permitem facilmente decidir se um objeto
faz parte ou não de um conjunto.
A coleção de objetos: a, b, *, &, gato, ♣, ./, impressora, F, quadrado, árvore,
m, n, P, S, Z, não poderia ser considerada como conjunto, pois não é fácil
identificar que objeto faz parte e que objeto não faz parte da coleção.
• Os objetos: são entidades reais (concretas, que existem no mundo real, tais
como, livros, canetas, disquetes, frutas, etc.) ou abstratas (entidades intangı́veis, que existem no mundo abstrato ou imaginário, tais como, números,
letras, vogais, arquivos, programas, comandos, etc.)
1
2
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• A propriedade comum: é a caracterı́stica que distingue aos objetos de um
conjunto com os objetos de outro conjunto, que caracteriza os objetos que
estão “dentro” do conjunto dos objetos que estão “fora” do conjunto.
Exemplo 1.1
Conjunto de letras: a, b, c, d, . . . , x, y, z
Exemplo 1.2
Conjunto de números inteiros . . . , −2, −1, 0, 1, 2, 3, 4, 5, . . .
Exemplo 1.3
Conjunto Famı́lia: pai, mãe, filho, filha
Exemplo 1.4
Conjunto Casa: sala, dormitório, banheiro, cozinha, copa, garagem
Exemplo 1.5
Conjunto time-futebol: goleiro, defesa, lateral, meio-campo, atacante
Exemplo 1.6
Conjuntos concretos: conjunto de computadores, conjunto de monitores, conjunto de placas de rede, conjunto de folhas de impressão, conjunto de
CD’s de programas gráficos, conjunto de alunos de Computação, etc.
Exemplo 1.7
Conjunto abstratos: conjunto de gatos sem cabeça, conjunto de
lâmpadas digitais, conjunto de livros sem folhas, conjunto de alfabetos sem letras,
conjunto de árvores sem raiz, conjunto de programas em linguagem Fortran, conjunto de programas Delphi, etc.
Definição 1.2 Elemento
Os objetos de um conjunto são chamados de elementos do conjunto. Um elemento
ou membro de um conjunto, é uma entidade básica a qual não é definida formalmente
e que possui a propriedade comum que caracteriza todos os objetos do conjunto.♦
Exemplo 1.8
Suponha que o conjunto Computador esta formado pelos objetos
processador, placa-mae, monitor, teclado, mouse, dispositivos E/S. Então podemos
dizer que, processador é um elemento do conjunto Computador.
Definição 1.3 Relação de Pertinência
O relacionamento entre um elemento e um conjunto é dado pela relação de pertinência. Este relacionamento, denotado pelo sı́mbolo ∈, indica quando um elemento
é membro ou não de um determinado conjunto.
Assim, se um elemento a é membro de um conjunto X, dizemos que o elemento
a pertence ao conjunto X e podemos escrever:
a∈X
Similarmente, se um elemento b não é membro de um determinado conjunto Y
(não possui a propriedade comum que caracteriza o conjunto Y), dizemos que b não
pertence ao conjunto Y, e escrevemos:
b 6∈ Y
3
1.3. REPRESENTAÇÃO GRÁFICA DE CONJUNTOS
Quando dois elementos p e q ambos pertencem a um conjunto X, então escrevemos p, q ∈X. Similarmente, no caso contrário, escrevemos p, q 6∈X
Definição 1.4 Notação de Conjuntos
Um conjunto qualquer A é denotado por duas chaves { e } junto com os elementos
dentro das chaves.
A = {elementos do conjunto}
Por comodidade e facilidade de leitura, o nome do conjunto, sempre se escreve com
letras maiúsculas (pelo menos a primeira letra do nome) e os nomes dos elementos
com letras minúsculas.
Exemplo 1.9
A = {a} é o conjunto unitário formado por um único elemento a
X = {P edro, Laura} é o conjunto composto de dois elementos P edro e Laura.
N6 = {1, 2, 3, 4, 5, 6} é o conjunto de números inteiros positivos menores que
7
Z5 = {. . . , −20, −15, −10, −5, 0, 5, 10, 15, 20, . . .} é conjunto de números inteiros que
são múltiplos de 5
Exemplo 1.10
A = {a, b, c, d}
X = {2, 5, 8}
F igGeom = {4, , }
a ∈ A, b, c, d ∈ A
2 ∈ X, a 6∈ X
∈ F igGeom
Exemplo 1.11 Conjuntos Numéricos
N = conjunto de todos os números inteiros não negativos
Z = conjunto de todos os números inteiros
Q = conjunto de todos os números racionais
R = conjunto de todos os números reais
C = conjunto de todos os números complexos
Definição 1.5 Ordem dos elementos
Em um conjunto qualquer, a ordem dos elementos não tem importância, isto é,
não existe o conceito de primeiro elemento, segundo elemento ou último elemento
do conjunto.
A = {a, b, c} = {b, c, a} = {c, a, b} = {a, c, b}
1.3
Representação Gráfica de Conjuntos
Para identificar graficamente quais elementos pertencem a um conjunto (e quais não
pertencem), utiliza-se esquemas gráficos construı́dos com curvas fechadas (cı́rculos,
4
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
elipses, etc.)junto com os elementos do conjunto dentro da curva fechada. Estes
gráficos são chamados de Diagramas de Venn. John Venn (1834-1923) foi um matemático inglês que publicou seu trabalho em 1880, em um artigo titulado “Sobre
representação diagramática e mecânica de proposições e raciocı́nios”.
Venn propôs a idéia de representar as relações entre conjuntos através de configurações de figuras no plano. O objetivo dele, claramente formulado naquele artigo:
...antes de mais nada os diagramas servem para auxiliar o olho e a mente graças a
natureza intuitiva do seu testemunho... foi plenamente alcançado, já que 125 anos
mais tarde todos os livros elementares de matemática usam este dispositivo gráfico
para introduzir nos alunos o conhecimento da Teoria de Conjuntos.
A
.13
.a
.x
.2
.7
.1
.b
.5
B
Figura 1.1: Diagramas de Venn para os conjuntos A e B
Inicialmente, Venn utilizou cı́rculos para representar conjuntos e relacionamentos
entre conjuntos (Fig. 1.2) e logo depois utilizou elipses (Fig. 1.3).
Y
A
X
B
Z
Figura 1.2: Diagramas de Venn para 2 e 3 conjuntos
5
1.4. ESPECIFICAÇÃO DE CONJUNTOS
Figura 1.3: Diagramas de Venn para 4 e 5 conjuntos
1.4
Especificação de Conjuntos
Indicar a caracterı́stica de todos os elementos de um conjunto, isto é, descrever a propriedade comum que caracteriza cada elemento de um conjunto, significa especificar
o conjunto.
Conjuntos podem ser especificados(descritos) de duas formas:
• Por Extensão: quando é possı́vel listar (enumerar) todos os elementos do conjunto.
Exemplo 1.12
A = {a, b, c, d, e}
Exemplo 1.13
B = {1, 2, 3, 5, 7, 11, 13, 19, 23, 29}
Exemplo 1.14
Linguagens = {Pascal, C++, Fortran, Basic, Lisp, Matlab}
Exemplo 1.15
Empresas = {IBM, Oracle, Sun, Dell, Intel, Brasoftware}
• Por Compreensão: indicando, estabelecendo a propriedade que caracteriza todos os elementos do conjunto. O conjunto A de todos os elementos a que
satisfazem a propriedade ρ é denotado por:
{a ∈ A/ρ(a)}
ρ(a) significa: “o elemento a satisfaz a propriedade ρ”, ou “ρ(a) é verdadeiro”.
Exemplo 1.16
jetos }
LinguagensObjeto = {L/L é uma linguagem Orientad a Ob-
6
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 1.17
Compiladores = {c/c é um compilador}
Obviamente, outros objetos tais como Eiffel, Smalltalk e C++ também são
elementos de LinguagensObjeto. Também, MS Visual C, C++ Builder, Compaq Fortran são elementos do conjunto Compiladores.
Outras formas de especificar um conjunto por compreensão:
{a ∈ A|ρ(a)} utilizando o separador | (barra vertical)
{a ∈ A : ρ(a)} utilizando o separador : (dois pontos)
Exemplo 1.18
N = {x : x ∈ N, x < 5}
P = {y : y ∈ Z, y é par }
L = {z|z ∈ H, z é divisı́vel por 7}
Definição 1.6 Conjunto Finito, Conjunto Infinito
Um conjunto qualquer A é dito ser finito se é possı́vel especificar o conjunto por extensão, o seja, listar todos os seus elementos. Caso contrário, isto é, quando somente
é possı́vel especificar tal conjunto por compreensão e não por extensão, dizemos que
o conjunto é infinito.
Exemplo 1.19 Conjuntos finitos:
A = { 2, 4, 5, 9, 23}
B = { a, b, c, d }
V = { a, e, i, o, u}
S = {a ∈ Z / 9 ≤ a ≤ 14} = {10, 12, 14}
Exemplo 1.20 Conjuntos infinitos:
Números Naturais N
Intervalo de números reais: 8 ≤ x < 15, onde x ∈ R
Conjunto de estrelas do céu.
Zp = {x ∈ Z / x é um número primo}
Definição 1.7 Conjunto Universal
Em qualquer aplicação da teoria dos conjuntos, os membros do conjunto de todos
os conjuntos de uma determinada área de aplicação, as vezes formam um conjunto
muito grande chamado Conjunto Universal ou Universo do discurso. É comum
denotar o conjunto universal de n conjuntos especı́ficos como a coleção de todos os
objetos desses n conjuntos. Este conjunto é denotado pela letra U.
O conjunto universal define o contexto ou ambiente dos objetos em discussão.
Exemplo 1.21
U = conjunto de todos os computadores
A = conj. computadores pessoais
B = conj. supercomputadores
7
1.5. CONJUNTOS ESPECIAIS
U=
U=
U=
U=
C = conj. computadores portáteis
conjunto de todas as linguagens de programação
X = conj. linguagens orientadas a objetos
Y = conj. de linguagens para Banco de Dados
V = conj. de linguagens visuais
LIA = conjunto de linguagens para Inteligência Artificial
conjunto de todos livros de Computação
conjunto de todas as letras do alfabeto
conjunto de todos os números inteiros
Exemplo 1.22
Se A={1, 5, 7}, B={3, 6, 15} e C={8, 25}, então U = Z
Definição 1.8 Conjunto vazio ou Nulo
O conjunto sem elementos, é chamado conjunto vazio, e é denotado pelo sı́mbolo ∅
ou por {}. Este conjunto é único.
Exemplo 1.23
- o conjunto de
- o conjunto de
- o conjunto de
- o conjunto de
- etc.
todas as linguagens de programação sem nome
livros lı́quidos
teclados sem caracteres
satélites da Lua
Definição 1.9 Elementos repetidos
Um elemento repetido mais de uma vez na especificação por extensão de um conjunto
representa um único elemento.
X = {a, b, a, c, b, a, a, c, d, b, c, a, b} = {a, b, c, d}
1.5
Conjuntos Especiais
Definição 1.10 Subconjunto, inclusão
Se cada elemento de um conjunto B é também um elemento de um conjunto A (ver
Fig. 1.4 esquerda), então afirma-se que B é um subconjunto de A, ou também
diz-se que o conjunto B esta contido ou incluı́do no conjunto A, ou que o conjunto A
contém ou inclui o conjunto B. Este relacionamento1 (de inclusão), é escrito como:
B ⊆ A or A ⊇ B
Exemplo 1.24
1
B = {2, 45, 168} e A = {1, 2, 3, 45, 120, 168, 200}. Logo B ⊆ A.
O relacionamento entre elementos e seu conjunto é indicado através da relação de pertinência
∈. Por exemplo, x ∈A. O relacionamento entre um subconjunto e seu conjunto, é indicado pela
relação de continência ⊆. Por exemplo, X⊆A
8
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 1.25
Se X ={a, b} e Y = {a, b, c, d} então X ⊆ Y
Exemplo 1.26 Se M = {x ∈ R/3 < x ≤ 7} e N = {y ∈ R/−1 ≤ y < 20} então M⊆N.
Definição 1.11 Subconjunto próprio
Um subconjunto N é dito ser um subconjunto próprio de M (ver Fig. 1.4 direita),
e denotamos por N⊂M, se:
• N é subconjunto de M, isto é, N⊆M
• Existe pelo menos um elemento x de M que não é elemento de N
Exemplo 1.27
Se P = {m, n} e Q = {m, n, t, u} então P⊂Q
A
.a
B .c .b
M
.p
.u
.y
N
.x
Figura 1.4: Subconjunto e Subconjunto próprio
Definição 1.12 Conjuntos Iguais
Os conjuntos A e B são iguais, e denotamos por A = B, se e somente se eles tem os
mesmos elementos, ou seja,
A = B se e somente se A ⊆ B e B ⊆ A
Exemplo 1.28
Seja A ={a, b, c} e B = {a, c, b, a, b, b, c}, então A = B
Observação.- O fato de dois conjuntos ter o mesmo número de elementos não
significa que eles sejam iguais, pois um conjunto é definido qualitativamente (propriedade comum) e não quantitativamente (número de elementos).
Definição 1.13 Conjunto Complemento
Seja A um subconjunto próprio de S, como mostrado na Fig.1.5, então S consiste
de todos os elementos de A junto com outros elementos que não estão em A. O
conjunto destes últimos elementos:
{x/x ∈ S, x 6∈ A}
constituem outro subconjunto próprio de S chamado o complemento de A em S.
O complemento de A é denotado por Ac
9
1.5. CONJUNTOS ESPECIAIS
Complemento
de A em S
S
A
S
.p
.y
.u
A
.x
Figura 1.5: Complemento de um conjunto
Exemplo 1.29 Seja S = {a, b, c, d} então
{a}c = {b, c, d} em S
{a, b}c = {c, d} em S
{a, b, c}c = {d} em S
{a, b, c, d}c = S c = ∅ em S.
Definição 1.14 Conjunto Potência
Dado um conjunto A qualquer, definimos o conjunto potência ou conjunto de
partes de A, e denotamos por P(A) ou 2A , como sendo o conjunto de todos os
sub-conjuntos de A.
Exemplo 1.30
A = { 2, 3, 7}
P(A) = 2A = {∅, {2}, {3}, {7}, {2, 3}, {2, 7}, {3, 7}, A}
Exemplo 1.31
B = {a, b}
P(B) = 2B = {∅, {a}, {b}, {a, b}}
Observação 1.- Os conjuntos ∅ (conjunto vazio) e A, sempre são elementos do
conjunto potência P(A)
Observação 2.- O número de elementos do conjunto potência de um conjunto
A, é dada pela fórmula:
n P(A) = n(2A ) = 2n(A)
onde n(A) é número de elementos do conjunto A
Exemplo 1.32
Exemplo 1.33
Se M = {a, b, c}, n(M )=3 então n P(M ) = 2n(M ) = 23 = 8
Se X = {3, 6, 7, 9, 15}, n(X)=5 e n P(X) = 2n(X) = 25 = 32
10
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
1.6
Cardinalidade
Definição 1.15 Cardinalidade de um conjunto
A cardinalidade de um conjunto A, denotada por #A ou n(A), é definida como
sendo o número de elementos do conjunto. Aparentemente, somente conjuntos finitos
poderiam ter cardinalidade, pois só deles poderiam-se verificar o seu número de
elementos. Porém, conjuntos infinitos também tem cardinalidade.
Além de #A ou n(A), em alguns textos de Matemática, também pode-se encontrar a cardinalidade de um conjunto denotada como card(A) ou |A|.
Exemplo 1.34
Se A={4, 7, 26} então #A = n(A) = card(A) = |A| = 3, pois o
número de elementos de A é 3.
Definição 1.16 Conjuntos Equipotentes
Dois conjuntos A e B são ditos equipotentes ou terem o mesmo número de elementos ou a mesma cardinalidade, se existe uma correspondência um-a-um (injetiva)2
se entre os elementos do conjunto A e os elementos do conjunto B.
• Um conjunto A é finito ou tem cardinalidade finita se A é vazio ou se A tem a
mesma cardinalidade do conjunto {1, 2, 3, ..., m} para algum inteiro positivo
m. Neste caso, #A = m.
• Um conjunto A é infinito se existe uma bijeção entre A e um subconjunto
próprio de A, isto é, se A tem um subconjunto próprio com a mesma cardinalidade.
• Um conjunto que tem a mesma cardinalidade que o conjunto de números
naturais N é dito ser contável ou contavelmente infinito. O termo contável
refere-se quase sempre a conjuntos finitos ou contavelmente infinitos.
Exemplo 1.35 O conjunto de números naturais ı́mpares NI é contavelmente infinito.
A função f (n) = 2n + 1 estabelece a correspondência injetiva entre N e NI.
Exemplo 1.36 Os pontos de uma grade infinita bidimensional pode ser usada para
mostrar que o produto cartesiano N × N é contável. A correspondência pode ser a
seguinte g(i, j) = ((i + j)(i + j + 1)/2) + i e mostrada como:
0
l
[0, 0]
2
1
l
[0, 1]
2
l
[1,0]
3
l
[0,2]
4
l
[[1,1]
5
l
[2,0]
6
l
[0,3]
7
l
[1,2]
...
...
O termo “correspondência injetiva”, “injeção”, “bijeção”, serão estudados na seção de Funções,
no final deste capı́tulo
1.7.
ÁLGEBRA DE CONJUNTOS
11
Teorema 1.1.
• A união de dois conjuntos contáveis é contável.
• O produto cartesiano de dois conjuntos contáveis é contável.
• O conjunto de sub-conjuntos finitos de um conjunto contável é contável.
• O conjunto de seqüências de tamanho finito de elementos de um conjunto
contável não vazio, é contavelmente infinito.
1.7
Álgebra de Conjuntos
Informalmente uma Álgebra é uma dupla < Ob, Op > formada por uma coleção de
objetos e um conjunto de operações definidas sobre estes objetos.
Definição 1.17 Álgebra de Conjuntos
É uma coleção de conjuntos com operações definidas sobre conjuntos
1.7.1
Operações Básicas entre Conjuntos
A seguir apresenta-se as operações básicas sobre conjuntos considerando sempre
que, em cada operação, temos um ou dois conjuntos A e B que pertencem ao mesmo
conjunto universal U, isto é, estão no mesmo contexto.
• Definição 1.18 União de Conjuntos
A união dos conjuntos A e B, denotada por A∪B, é definida por:
A ∪ B = {x/x ∈ A ou x ∈ B}
• Definição 1.19 Intersecção de Conjuntos
A intersecção (ou interseção) dos conjuntos A e B, denotada por A∩B, é
definida por:
A ∩ B = {x/x ∈ A e x ∈ B}
• Definição 1.20 Complemento de um conjunto
O complemento de um conjunto A⊆U, denotado por A0 , Ac , ∼A ou C(A), é
definido por:
A0 = Ac = {x/x ∈ U e x 6∈ A}
12
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• Definição 1.21 Diferença de Conjuntos
A diferença dos conjuntos A e B, denotado por A-B, é definido por:
A − B = {x/x ∈ A e x 6∈ B}
B
A
A∩B
A∪B
B
A
B
A
A-B
Conjunto Universal
Ac
U
A
Figura 1.6: Operações básicas entre conjuntos
Exemplo 1.37 Seja A = {a, b, c, d}, B = {c, d, , e, f, g}, e C = {b, c, e, g}, então
A∪B = {a, b, c, d, e, f, g}
A∩B = {c, d}
A∪C = {a, b, c, d, e, g}
A∩C = {b, c}
A-B = {a, b}
A-C = {a, d}
Exemplo 1.38 Se M = {3, 4, 6, 8} e N = {4, 8}, logo
M∪N = {3, 4, 6, 8}, M∩N = {4, 8}, e M-N = {3, 6}
O conjunto potência pode ser considerado como uma operação unária sobre um
conjunto qualquer A:
2A = {S|S ⊆ A}
Similarmente, o produto cartesiano (será visto no próximo capı́tulo), pode ser
considerado como uma operação entre dois conjuntos:
A × B = {(a, b)/a ∈ A e b ∈ B}
Definição 1.22 Conjuntos Disjuntos
Dois conjuntos A e B são disjuntos se eles não tem nenhum elemento comum, isto
é, se A∩B = ∅.
Exemplo 1.39
A = {a, b, c} e B = {d, ef } são disjuntos pois A∩B = ∅
Exemplo 1.40
G = {2, 5, 7} e H = {3.1, 4.8, 9.99} são disjuntos, pois G∩H = ∅
1.7.
13
ÁLGEBRA DE CONJUNTOS
Tabela 1.1: Álgebra de Conjuntos
Lei Equivalência
Idempotência A ∪ A = A
A∩A=A
Associativa A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C
Comutativa A ∪ B = B ∪ A
A∩B =B∩A
Distributiva A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Identidade A ∪ ∅ = A
A∪U =U
A∩U =A
A∩∅=∅
Complemento A ∪ Ac = U
A ∩ Ac = ∅
Uc = ∅
∅c = U
Involução (Ac )c = A
Absorção A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A
De Morgan (A ∪ B)c = Ac ∩ B c
(A ∩ B)c = Ac ∪ B c
Diferença A − B = A ∩ B c
Diferença Simétrica A ⊕ B = (A ∪ B) − (A ∩ B)
1.7.2
Álgebra de Conjuntos
Conjuntos sob as operações básicas de união, intersecção e complemento satisfazem
várias leis ou identidades (na forma de igualdades). Estas identidades são utilizadas
para facilitar e justificar a prova de outras operações mais complexas com conjuntos. Desta forma, cada vez que for necessário fazer uma prova em operações com
conjuntos, será necessário indicar qual identidade foi utilizada.
Na Tabela 1.1, apresenta-se uma lista básica de identidades L1 = L2 que são
utilizadas na Álgebra de Conjuntos:
Exemplo 1.41
Provar que (A ∪ B) ∩ (A ∪ B c ) = A.
(A ∪ B) ∩ (A ∪ B c )
Prova
= A ∪ (B ∩ B c )
= A∪∅
=A
Lei distributiva L2=L1
Lei do Complemento ∩
Lei de identidade
14
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 1.42
Provar que A ∪ (A ∩ B) = A.
A ∪ (A ∩ B)
Exemplo 1.43
=
=
=
=
Prova
(A ∪ A) ∩ (A ∪ B)
A ∩ (A ∪ B)
A∩U
A
Lei distributiva L1=L2
Lei de Idempotência ∪
Def. de Universo A∪B = U
Lei de Identidade
Provar que [C ∩ (A ∪ B)] ∪ [(A ∪ B) ∩ C c ] = A ∪ B.
[C ∩ (A ∪ B)] ∪ [(A ∪ B) ∩ C c ]
Prova
=
=
=
=
[(A ∪ B) ∩ C] ∪ [(A ∪ B) ∩ C c ]
(A ∪ B) ∩ (C ∪ C c )
(A ∪ B)∩U
A∪B
(comutativa)
(distributiva)
(complemento)
(identidade)
Existem dois métodos para provar equações L1 = L2 sobre conjuntos utilizando
Álgebra de Conjuntos:
• Fixando um elemento x que satisfaz, primeiro o lado esquerdo L1, e logo aplicando as identidades da Álgebra de Conjuntos, mostrar que também satisfaz
o lado direito L2. Aqui usamos a definição de igualdade de conjuntos: A = B
se e somente se A⊆B e B⊆A. O seja mostrar que L1⊆L2 e logo L2⊆L1
• Utilizando Diagramas de Venn (com uma cor diferente para cada conjunto)
Definição 1.23 Dualidade de Expressões
Seja E uma expressão formada por operações sobre conjuntos. Então o dual E∗ de
E, é outra expressão obtida ao substituir cada ocorrência de ∪, ∩, U e ∅ em E, por
∩, ∪, ∅ e U, respectivamente.
Exemplo 1.44
1.8
O dual de (A ∩ U ) ∩ (∅ ∪ Ac ) é a expressão (A ∪ ∅) ∪ (U ∩ Ac )
Definições Recursivas
Definição 1.24 Definição Recursiva
Uma definição recursiva de um conjunto X especifica um método para a construção do conjunto. Esta definição utiliza duas componentes: a base e o conjunto
de operações.
• A base consiste de um conjunto finito de elementos que são explicitamente
designados como elementos do conjunto X.
15
1.9. SEQÜÊNCIAS
• As operações são utilizadas para construir novos elementos do conjunto, a
partir dos elementos previamente definidos.
Então, o conjunto X definido recursivamente é o conjunto de todos os elementos
que podem ser gerados a partir dos elementos da base por um número finito de
aplicações das operações.
Exemplo 1.45
A definição recursiva de N, o conjunto de números naturais, é
construı́da usando a função sucessor succ.
• Base: 0 ∈N
• Passo Recursivo: Se n ∈ N, então succ(n) ∈ N
• Fecho: n ∈N somente se este pode ser obtido a partir de 0 por um número
finito de aplicações da operação succ.
Exemplo 1.46
Definição recursiva da Soma (adição):
• Base: Se n = 0, então m + n = m
• Passo recursivo: m + succ(n) = succ(m + n)
• Fecho: m + n = k somente se a igualdade pode ser obtida de m + 0 = m
usando um número finito de aplicações do passo recursivo.
1.9
Seqüências
Uma coleção de objetos pode ser agrupada utilizando algumas estruturas matemáticas.
A maneira mais simples vista até agora é sob o conceito de conjunto. Outras estruturas são: matrizes, álgebras, seqüências, etc.
Definição 1.25 Seqüência
Seqüência é uma lista indexada (ordenada) de objetos chamados termos ou componentes e é denotada listando os objetos entre parênteses:
(o1 , o2 , . . . , on )
Em uma seqüência, a cada termo está associado um ı́ndice (número natural)
Outra definição: Uma seqüência é uma estrutura discreta usada para representar
uma lista ordenada de objetos.
Exemplo 1.47
(a, b, c, d) é uma seqüência de quatro termos
16
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 1.48 Consideremos a seqüência (bm ), onde bm = 1/n. A lista de termos
da seqüência (b1 , b2 , . . .) é
1 1 1
(1, , , , . . .)
2 3 4
Conjuntos e seqüências na Matemática desempenham roles de reunião, ajuntamento, coleção de objetos. Porém existem algumas diferenças entre as duas estruturas:
• Todos os elementos de um conjunto são diferentes (elementos especificados
como repetidos representam o mesmo elemento). Termos em uma seqüência
podem ser especificados como repetidos representando termos diferentes. Por
exemplo, (a, b, a) é uma seqüência válida de três termos, porém, {a, b, a, b, a}
é um conjunto de dois elementos {a, b}
• Os termos de uma seqüência tem um ordem especificado (ı́ndice). os elementos
de um conjunto não tem ordem. Por exemplo, as seqüências (x, y, z) e (z, y, x)
são diferentes, enquanto que, os conjuntos {x, y, z} e {z, y, x} são iguais.
• O conjunto vazio é denotado pelo sı́mbolo ∅, enquanto que a seqüência vazia
é denotado pelo sı́mbolo λ
Uma generalização e formalização de seqüências de elementos será descrita no seção
??
Um problema muito comum em Matemática Discreta é encontrar uma fórmula
matemática ou regra geral que permita construir o conjunto de termos de uma
seqüência. Assim por exemplo,
n2 : regra para produzir o quadrado dos naturais (1, 4, 9, 16, 25, . . .)
2n : regra para produzir a seqüência (2, 4, 8, 16, 32, 64, 128, 256, 512, . . .)
n(n + 1)/2 : regra para produzir a seqüência (1, 3, 6, 10, 15, . . .)
1.10
Relações
Definição 1.26 Relação
Sejam A e B dois conjuntos qualquer. Uma relação binária R é uma subconjunto
do produto cartesiano A×B. Em outras palavras, uma relação binária R, é um
conjunto de pares ordenados, onde cada primeiro elemento pertence ao conjunto A
e cada segundo elemento pertence ao conjunto B.
R = {(a, b)|a ∈ A, b ∈ B}
Se R ⊆ A × B, então:
17
1.10. RELAÇÕES
• A é chamado o domı́nio da relação
• B é chamado o contra-domı́nio (ou codomı́nio) da relação
Visualização de Relações Binárias Quando o conjunto B é o mesmo conjunto
A, isto é, quando R ⊆ A × A, é dita uma relação sobre A.
Uma relação pode ser ”visualizada” através de quatro formas gráficas, como
mostra a Fig. 1.7:
• Tabelas: pares com interseção 1 são elementos da relação
• Diagramas de Venn: conjuntos e setas relacionando elementos
• Grafos direcionados: vértices são os elementos e, arestas (arcos) são os
relacionamentos.
• Conjuntos: de pares ordenados
B
A
x
1 0
2 0
3 0
y
1
0
1
A
z
1
0
0
.1
1= relacionado
0 = não relacionado
R
Tabelas
3
R
.x
.2
.y
.3
.z
Diagrama de Venn
1
Grafo
direcionado
B
R
2
Lista (conjunto)
4
R= { (a1 , b1 ), (a1 , b3 ), (a3 , b3 ) }
Figura 1.7: Visualização gráfica de uma relação
Tipos (Propriedades) de Relações.- Dados dois conjuntos A e B, então, temos
três tipos de relações:
Relação Reflexiva , se para todo a ∈ A, temos (a, a) ∈ R
Relação Simétrica , se (a, b) ∈ R, então (b, a) ∈ R.
Relação Antissimétrica , se (a, b) ∈ R e (b, a) ∈ R então a = b
Relação Transitiva , se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R
18
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Relação de Ordem.- Seja A um conjunto qualquer e R uma relação em A. Então
R é uma:
Relação de Ordem , se é transitiva.
Relação de Ordem Parcial , se é reflexiva, antissimétrica e transitiva.
Relação de Ordem Total , se é uma relação de ordem parcial e, para todo
par a, b ∈ A, ou (a, b) ∈ R ou (b, a) ∈ R
Exemplo 1.49
• A relação ⊆ (inclusão de conjuntos) é uma relação de ordem parcial sobre
qualquer coleção de conjuntos.
• A relação ≤ sobre o conjunto R de números reais, é reflexiva, antisimétrica e transitiva (ordem parcial)
• R = {(a, b)|b = ar para algum inteiro positivo r} é de ordem parcial sobre Z
Relação de Equivalência.- Sejam A um conjunto qualquer e R uma relação em
A. Então R é uma relação de equivalência se for reflexiva, simétrica e transitiva.
Exemplo 1.50
A classificação de animais por espécies, isto é, a relação ”é
da mesma espécie como”, é uma relação de equivalência sobre o conjunto dos
animais.
Exemplo 1.51 Seja m um inteiro positivo fixo. Dois inteiros a e b diz-se ser
congruentes modulo m, escrito a ≡ b (mod m), se m divide a − b.
Uma relação de equivalência R sobre um conjunto A, induz um particionamento do conjunto A em subconjuntos disjuntos e não vazios denominados
classes de equivalência
[a] = {x|(a, x) ∈ R}
Qualquer b ∈ [a] é chamado um representante da classe de equivalência.
Exemplo 1.52
Seja R sobre S = {1, 2, 3}.
R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
então [1] = {1, 2} [2] = {1, 2} [3] = {3}
Fecho de uma relação.- Considere um conjunto qualquer A e a coleção de todas
as relações sobre A. Seja P uma propriedade de tais relações.
• Uma relação com a propriedade P será chamada uma P-relação. Então
o Fecho de R respeito da propriedade P, ou P-fecho, é a menor
relação que contém R e que satisfaz a propriedade P
R ⊆ P(R) ⊆ S
para cada relação S que contém R
19
1.10. RELAÇÕES
• R+: O fecho de R em relação ao conjunto de propriedades {transitiva},
denominado Fecho transitivo de R e denotado por R+, é definido como
segue:
– Se (a, b) ∈ R, então (a, b) ∈ R+
– Se (a, b) ∈ R+ e (b, c) ∈ R+, então (a, c) ∈ R+
– os únicos elementos de R+ são os construı́dos como acima;
• R*: O fecho de R em relação ao conjunto de propriedades {transitiva,
reflexiva}, denominado Fecho Transitivo e Reflexivo de R e denotado
por R*, é tal que:
R∗ = R+ ∪ {(a, a)|a ∈ A}
1
1
5
5
2
2
Grafo
6
3
6
3
Fecho
4
4
Figura 1.8: Grafo e respectivo fecho
Exemplo 1.53 Fecho de um Grafo visto como uma Relação.
Um grafo pode ser definido como uma relação A de arestas em um conjunto
de V de vértices:
A = {((1, 2), (2, 3), (3, 4), (1, 5), (5, 6)}
é um grafo em V = {1, 2, 3, 4, 5, 6} como ilustrado na Fig. 1.8 (esquerda), onde
o par ordenado que define uma aresta é representado por uma seta na qual
as circunferências de origem e de destino representam a primeira e a segunda
componente do par, respectivamente. O fecho transitivo e reflexivo:
A∗ = {(1, 1), (1, 2), (1, 3), (1, 3), (1, 4), (1, 5), (1, 6), ...}
onde as arestas adicionadas pelo fecho são representadas por um traço diferente.
20
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
1.11
Funções
Definição 1.27 Função, Função Parcial
Uma função parcial f ou simplesmente função f , e denotada por
f : A −→ B
é uma relação f ⊆ A × B tal que se (a, b) ∈ f e (a, c) ∈ f , então b = c. Em outras
palavras, uma função parcial é uma relação onde cada elemento do domı́nio está
relacionado com um único elemento do contradomı́nio. Se (x, y) pertence à função
então escrevemos f (x) = y
Se (x, y) ∈ f então dizemos que y é a imagem de x sob f , e dizemos também
que f esta definida em x. Em Computação costuma-se dizer que f (x) é o valor
da função f no parâmetro x
• A é conjunto de partida e B é o conjunto de chegada da função f
• O conjunto
{a ∈ A/ existe b ∈ B com f (a) = b}
é denominado domı́nio de f e é denotado por Dom(f ).
• O conjunto
{b ∈ B/ existe a ∈ A com f (a) = b}
é denominado conjunto imagem de f e é denotado por f (A) ou Img(f ).
Figura 1.9: Função entre dois conjuntos A e B
Exemplo 1.54
Sejam A = {1, 2, 3, 4} e B = {1, 3, 5, 7, 9} e f : A −→ B
f = {(1, 3), (2, 1), (4, 5)}
21
1.11. FUNÇÕES
Dom(f ) = {1, 2, 4} ⊆ A
Img(f ) = {1, 3, 5} ⊆ B
Exemplo 1.55
Sejam M = {a, b, c, d} e N = {2, 3, 4, 7, 8} e g : M −→ N
g = {(a, 3), (c, 2), (a, 7), (b, 3)}
então g não é função, devido a que o elemento a de M está relacionado com mais de
um elemento (3 e 7) de N : (a, 3) e (a, 7)
Definição 1.28 Função Total ou Aplicação
Uma função total é uma função parcial f : A −→ B onde para todo elemento
a ∈ A existe um b ∈ B tal que f (a) = b. Em outras palavras, uma função total é
uma função parcial definida para todos os elementos do conjunto de partida de f .
Exemplo 1.56
então
Seja d = {3, 4, 7} −→ {7, 9, 10, 15, 19} definida por d(x) = 2x + 1,
d = {(3, 7), (4, 9), (7, 15)}
é total.
Definição 1.29 Composição de Funções
Sejam duas funções f : A −→ B e g : B −→ C (Fig.1.10), então definimos a função
composta de de f e g do conjunto A para o conjunto C, e denotamos por g ◦ f .
como
(g ◦ f )(a) = g(f (a))
Figura 1.10: Composição de funções
Exemplo 1.57 Seja A = {2, 3, 5}, B = {a, b, c, d}, C = {3, 4, 5, 9}
f = {(2, b), (3, a), (5, d)}
g = {(a, 3), (b, 4), (c, 5)}
então:
g ◦ f = {(2, 4), (3, 3)}
Exemplo 1.58 Sejam h e k funções definidas sobre o conjunto dos números inteiros
Z da seguinte forma: h(x) = x2 + x, e k(y) = y + 5, então:
(k ◦ h)(x) = k(h(x)) = k(x2 + x) = (x2 + x) + 5
22
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Definição 1.30 Função Inversa
Seja f : A −→ B uma função, então
• Dom(f ) ⊆ A
• Img(f ) ⊆ B
• f −1 (Img(f )) denota o conjunto de elementos a de A tal que a sua imagem
pertence a Img(f ), como mostrada na Fig.1.11. O conjunto f −1 (Img(f )) ⊆A
é chamada de imagem inversa ou pre-imagem de f (Dom(f )). f −1 é chamada de função inversa de f
Se f : A −→ B é definida por
f = {x, y)/x ∈ A, y ∈ B e f (x) = y}
então
f −1 = {y, x)/y ∈ B, x ∈ A, e f −1 (y) = x}
Figura 1.11: Função inversa f −1 : B −→ A
Definição 1.31 Função Identidade
A função identidade sobre um conjunto A, denotada por IA , é uma função
IA : A −→ A
onde cada elemento a ∈A esta relacionado consigo mesmo IA (a) = a
Definição 1.32 Função Invertı́vel
Uma função f : A −→ B, é chamada de invertı́vel, se existe a função inversa
f −1 : B −→ A, talque
f −1 ◦ f = IA
e f ◦ f −1 = IB
23
1.12. INDUÇÃO MATEMÁTICA
Definição 1.33 Restrição
Se f : A −→ B e A1 ⊆ A então
f |A1 : A1 −→ B
é chamada a restrição de f a A1 , se f |A1 (a) = f (a) para todo a ∈ A1
Definição 1.34 Extensão
Seja A1
subseteqA e seja f : A1 −→ B. Se g : A −→ B tal que g(a) = f (a) para todo
a ∈ A1 então a função g é chamada de extensão de f a A.
Definição 1.35 Tipos de Funções
Uma função f : A −→ B é chamada:
• Função Injetiva (um-a-um): se para todo b ∈ B, existe no máximo um a ∈ A
tal que f (a) = b
• Função Sobrejetiva: se, para todo b ∈ B, existe pelo menos um a ∈ A tal
que f (a) = b.
• Função Bijetiva ou Isomorfismo: se é injetora e sobrejetiva
Exemplo 1.59
Injetiva: Para cada aluno da Universidade existe um número de
matrı́cula. Para cada aluno matriculado, existe um único número de matrı́cula.
Neste caso, existe uma relação injetiva (um-a-um) entre o conjunto de alunos e o
conjunto de números de matrı́cula
Exemplo 1.60
sobrejetiva: f : R → R definida por f (x) = 2x − 3. Para cada
y = f (x) existe um x ∈ R da forma (y + 3)/2
1.12
Indução Matemática
Definição 1.36 Princı́pio de Indução Matemática I
Seja P uma proposição definida sobre o conjunto dos números inteiros N, isto é, P (n)
ou é falso ou é verdadeiro para cada n ∈ N. Suponha-se que P tem as seguintes
propriedades:
1. P (n) é verdadeiro
2. P (n + 1) é verdadeiro quando P (n) é verdadeiro
Então, P é verdadeiro para cada inteiro positivo
Definição 1.37 Princı́pio de Indução Matemática II
Seja P uma proposição definida sobre os inteiros positivos N tal que:
24
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
1. P (1) é verdadeiro
2. P (n) é verdadeiro quando P (k) é verdadeiro para todo 1 ≤ k < n
Então, P é verdadeiro para cada inteiro positivo
Uma prova indutiva consiste de três etapas distintas:
• Provar que a propriedade P vale para cada elemento de um Conjunto Base X0 .
• Estabelecer uma hipótese indutiva: a suposição que a propriedade P vale para
cada elemento nos conjuntos X0 , X1 , ...,Xn
• Passo Indutivo: usando a hipótese indutiva, provar que a propriedade P vale
para cada elemento do conjunto Xn+1
Exemplo 1.61
Provar que
n
X
i=
i=0
Base: n = 0
0
X
n(n + 1)
2
i = 0 = 0(0 + 1)/2
i=0
Hipótese indutiva: Assumimos que para k = 1, 2, ..., n vale
k
X
i=
i=0
k(k + 1)
2
Passo indutivo: Temos que provar que
n+1
X
i=0
i=
(n + 1)(n + 1 + 1)
2
Em efeito:
n+1
X
i=o
i=
n
X
i=0
Exemplo 1.62
isto é,
!
i
+ (n + 1) =
n(n + 1)
n
(n + 1)(n + 2)
+ (n + 1) = (n + 1)( + 1) =
2
2
2
Provar que a soma dos n primeiros números ı́mpares é igual a n2 ,
1 + 3 + 5 + · · · + (2n − 1) = n2
Base: n = 3
1 + 3 + (2 ∗ 3 − 1) = 1 + 3 + 5 = 9 = 32
25
1.13. GRAFOS
Hipótese indutiva: Assumimos que para k = 1, 2, ..., n vale
1 + 3 + 5 + · · · + (2k − 1) = k 2
Passo indutivo: Temos que provar que
1 + 3 + · · · + (2k − 1) + (2(k + 1) − 1) = (k + 1)2
Em efeito,
1 + 3 + · · · + (2k − 1) + (2(k + 1) − 1) =
=
=
=
=
1.13
1 + 3 + · · · + (2k − 1) + (2(k + 1) − 1)
[k 2 ] + (2(k + 1) − 1)
k 2 + (2k + 2 − 1)
k 2 + 2k + 1
(k + 1)2
Grafos
Informalmente, podemos dizer que um grafo é um conjunto não vazio de nós (vértices)
e um conjunto de arcos (arestas), de modo que, cada arco conecta dois nós
Definição 1.38 grafo, grafo não-direcionado
Um grafo não direcionado ou simplesmente grafo, é uma tripla ordenada
G = (N, A, g)
onde, N é um conjunto não vazio de nós (vértices), A é um conjunto de arcos
(arestas) e, g é uma função que associa cada arco a a um par não ordenado x, y de
nós, chamados extremidades de a.
Figura 1.12: Grafo
Definição 1.39 grau de um vértice
O grau de um vértice é o número de arcos (arestas) que incidem neste vértice.
26
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
No exemplo da Fig.1.12, o grau do vértice e é 3, o grau do vértice c é 4, e o grau
do vértice f é 0 (nenhuma aresta incide neste vértice).
Definição 1.40 grafo direcionado
Um grafo direcionado (digrafo) é uma tripla ordenada
G = (N, A, g)
onde, N é um conjunto não vazio de nós, A é um conjunto de arcos, g é uma função
que associa cada arco a a um par ordenado (x, y) de nós, onde x é o ponto inicial
de a, e y é o ponto final de a
Figura 1.13: Grafos direcionados
Grafo Rotulado e grafo com pesos
q Grafo
rotulado
Definição 1.41 grafo rotulado,
grafo com
pesos
Um grafo rotulado é um grafo que
contém
identificadoras
ou rótulos ou
É um
grafo informações
que contém informações
identificadoras
nos vértices e/ou nas arestas. Um
grafo
com
pesos
é
o
grafo
onde
cada arco
rótulos nos vértices e/ou nas arestas
(aresta) tem um valor numérico (peso) associado.
q
Grafo com pesos
É o grafo onde cada arco (aresta) tem um valor numérico
(peso) associado
Brasilia
614
870
1614
Belo Horizonte
434
586
429
Porto Alegre
1109
Rio de Janeiro
São Paulo
UNASP – Matemática Discreta - GRAFOS - Prof. Dr. Ausberto S. Castro Vera
Figura 1.14:
Grafo rotulado e com pesos
Definição 1.42 subgrafo
Dizemos que o grafo A é um subgrafo do grafo B, se:
1. os vértices de A formam um subconjunto dos vértices de B
10
27
1.13. GRAFOS
2. as arestas de A também são arestas de B sobre os vértices correspondentes,
i.e., se a função g(a, e) é uma aresta do grafo A, então g(a, e) também é uma
aresta do grafo B
Figura 1.15: Subgrafo
Exemplo 1.63
Na Fig.1.15, o grafo A é subgrafo de B.
Definição 1.43 Caminho, comprimento
Um caminho em um grafo, é uma seqüência alternada de vértices e arestas
v0 , a0 , v1 , a1 , v2 , a2 , . . . , vn−1 , an−1 , vn
onde cada aresta ai contém os vértices vi e vi+1 . O comprimento ou tamanho de
um caminho é o número de arestas que ele contém.
Definição 1.44 grafo conexo
Um grafo conexo é aquele onde existe um caminho entre qualquer par de seus
vértices, isto é, existe um caminho de um vértice dado para qualquer outro vértice
do grafo.
Figura 1.16: Grafos conexo e não-conexo
O grafo G da Fig.1.16 (esquerdo) é conexo, enquanto que o grafo H (direita) não é
conexo, pois não existe nenhum caminho entre o vértice x e os vértices y ou z.
Definição 1.45 ciclo, grafo acı́clico
Um ciclo em um grafo é um caminho de um vértice vi para ele mesmo, tal que
28
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
nenhum arco ou vértice aparece mais de uma vez, exceto vi , isto é, um ciclo é um
caminho que começa e termina no mesmo vértice vi . Um grafo acı́clico é um grafo
sem ciclos.
Definição 1.46 grafo atravessável, grafo euleriano
Um grafo atravessável é aquele onde existe um caminho que inclua todos os
vértices e utilize cada aresta exatamente uma vez. Um grafo é euleriano se existe
uma trilha (caminho) atravessável fechada.
Definição 1.47 grafo hamiltoniano
Um grafo hamiltoniano é aquele que admite um caminho fechado que visita todos
os vértices exatamente uma vez cada um.
Em um grafo euleriano podem-se repetir os vértices e num grafo hamiltoniano
podem-se repetir as arestas.
(a)
(b)
Ponto de partida-chegada
Figura 1.17: (a) Grafo Euleriano. (b) Grafo Hamiltoniano
1.14
Árvores
Informalmente, definimos uma árvore como sendo um grafo conexo acı́clico direcionado com um vértice especial denominado raiz.
29
1.14. ÁRVORES
raiz
raiz
raiz
Figura 1.18: Exemplos de árvores
Geralmente em computação, costuma-se desenhar uma árvore com o vértice raiz
no topo do grafo
Definição 1.48 Árvore
Uma árvore é uma estrutura (N,A,r), onde N é o conjunto de nós, A é o conjunto
de arestas (relação de adjacência entre nós) e r ∈ N é a raiz da árvore.
Definição 1.49 Definição recursiva de árvore
• Um único nó é uma árvore. Esse nó é a raiz da arvore.
• Se A1 , A2 , . . . , An são árvores com raı́zes r1 , r2 , . . . , rn respectivamente, e r é
uma raı́z qualquer, então A1 A2 . . . An r é uma árvore, onde r esta ligado a
r1 , r2 , . . . rn
• Os nós r1 , r2 , . . . , rn são chamados de filhos de r, e o nó r é chamado de pai
de r1 , r2 , . . . , rn . Um filho de uma raı́z é chamdo também de sub-árvore
r
r2
r1
A1
A2
Figura 1.19: Definição recursiva de árvore
r
30
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
1.14.1
r1
Propriedades e definições
• Considerando que uma árvore é um grafo conexo acı́clico, existe um caminho
da raiz para qualquer nó e esse caminho é único.
• A profundidade (altura) de uma árvore é o comprimento do caminho
mais comprido da raiz até um dos nós. A profundidade
pode ser dado em
A1
termos de nós ou arestas. Equivalentemente, o nı́vel de um vértice (nó) v
é o comprimento de um caminho simples da raiz até o vértice v. A raiz tem
profundidade zero.
• Um nó sem filhos é chamado de folha ou nó terminal da árvore. As folhas
são vértices de grau 1. Excepcionalmente, a raiz também pode ser um vértice
de grau 1. Todos os nós que não são folhas são chamados de nós internos ou
nós não-terminais.
• Uma árvore binária é aquela que tem unicamente dois filhos: esquerdo e
direito
raiz
1
nó interno
2
3
folhas
Figura 1.20: Folhas, nós internos e profundidade
1.15
Exercı́cios
1. Apresentar uma lista de cinco conjuntos especificados por extensão e cinco
conjunto especificados por compreensão.
2. Listar os elementos dos seguintes conjuntos
• A = {x ∈ N/x divide a 48}
• B = {y ∈ N/4 + y = 3}
3. Quais destes conjuntos são iguais: {r, s, t}, {s, t, r, s}, {t, s, t, r}, {s, r, s, t}?
A2
31
1.15. EXERCı́CIOS
4. Ilustrar com os Diagramas de Venn a lei distributiva A ∩ (B ∪ C) = (A ∩ B) ∪
(A ∩ C)
5. Seja X = {a, b, c} e Y = {0, 1}. Listar todos os elementos de X × Y e todos
os subconjuntos de X × Y.
6. Dar um exemplo de uma relação sobre N × N que seja reflexiva e simétrica,
porém, não transitiva.
7. Considere a relação
R = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)}
sobre A = {1, 2, 3, 4}
(a) Indicar se R é reflexiva, simétrica ou transitiva.
(b) Que é necessário pra que R seja reflexiva? Simétrica?
(c) Faça um gráfico da relação R
8. Para cada uma das seguintes relações binárias em N, escrever cinco pares
ordenados:
(a) xRy se e somente se x + y < 7.
(b) xRy se e somente se x = y + 2.
(c) xRy se e somente se 2x + 3y = 10.
9. Dados os conjuntos A = {1, 2, 3, 4}, B = {x, y, z} e a relação entre A e B:
R = {(1, y), (1, z), (3, y), (4, x), (4, z)}
(a) Determinar a matriz (tabela) da relação R de A para B
(b) Desenhar o grafo da relação R
(c) Indicar o domı́nio e o contradomı́nio da relação R
10. Seja P o conjunto de pessoas que moram em São Paulo. Teste se as relações
binárias em P são reflexivas, simétricas, transitivas ou anti-simétricas
(a) xRy se e somente se x é, pelo menos, tão alto quanto y
(b) xRy se e somente se x é filho ou filha de y
(c) xRy se e somente se x tem os mesmos pais que y
(d) xRy se e somente se x é marido de y
(e) xRy se e somente se x tem a mesma altura que y
11. Seja A={1, 2, 3, ..., 8, 9} y seja R uma relação sobre o produto cartesiano A×A
definido por: (a, b)R(c, d) se a + d = b + c
32
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
(a) Provar que R é uma relação de equivalência
(b) Encontrar a classe de equivalência de (2,5) ou seja [(2, 5)]
12. Determinar se cada função é injetora:
(a) A cada pessoa é atribuı́do um número que corresponde a sua idade
(b) A cada paı́s é atribuı́do uma latitude e uma altitude correspondente a
sua capital
(c) A cada livro escrito por um único autor é atribuı́do o nome do autor
(d) A cada pais que tem primeiro ministro é atribuı́do o sobrenome do primeiro ministro
(e) A cada pessoa que tem conta no banco é atribuı́do o número de CPF
13. Seja f = {(1, 3), (2, 1), (3, 4), (4, 3)} e g = {(1, 2), (2, 3), (3, 1), (4, 1)}
(a) Determinar Dom(f ) e Img(g)
(b) Determinar as funções compostas: (f ◦ g), (g ◦ f ) e (f ◦ f )
14. Dar uma definição recursiva da operação de multiplicação de números naturais
usando as operações succ e adição.
15. Dar uma definição recursiva para o conjunto de pontos (x, y) sobre a linha
y = 5x + 1 em N × N. Utilize a operação succ.
16. Dar uma definição recursiva da operação
0
se n = 0
pred(n) =
n − 1 em outro caso
utilizando o operador succ.
17. Provar que 1 + 2 + 22 + ... + 2n = 2n+1 − 1 para todo n ≥ 0.
18. Provar por indução que 3 é fator de n3 − n + 3 para todo n ≥ 0.
19. Dar cinco exemplos de grafos rotulados
20. Qual é a diferença entre um grafo euleriano e um grafo hamiltoniano?. Dar
dois exemplos gráficos.
Capı́tulo 2
Linguagens
Em um contexto bem genérico, o termo linguagens significa considerar um conjunto
de categorias de linguagens: linguagens naturais (Português, Espanhol, Inglês, etc.),
linguagens de programação (Pascal, C++, Fortran, Java, Matlab, etc.), linguagens
matemáticos (lógica, λ-cálculo, conjuntos, álgebras, categorias), etc. Uma definição
geral deve ser considerada para qualquer tipo de linguagem. Neste capı́tulo, estamos
interessados em definir e utilizar as linguagens formais utilizadas na implementação
de autômatos e compiladores, para isto apresentamos uma definição de linguagem
baseada na teoria de conjuntos: uma linguagem é um conjunto de strings (cadeias
de caracteres) construı́das a partir de um conjunto de sı́mbolos de um alfabeto.
Linguagens que servem para nosso interesse computacional não são construı́dos
a partir de strings arbitrários, e sim a partir daqueles que satisfazem determinadas
propriedades. Estas propriedades constituem a sintaxe da linguagem.
2.1
Palavras
Definição 2.1 sı́mbolo
Um sı́mbolo é uma entidade abstrata que representa uma única idéia ou conceito,
e utilizada na Matemática e na Computação, na forma de objetos, para construir
determinados conjuntos. Após a definição do conjunto, os sı́mbolos são os elementos
de tal conjunto.
Exemplo 2.1
a, b, c, d, 0, 1, 2, 3, 4, α, β, δ, ∆, λ, ω, Ω, π, , ‡, , , , F
Exemplo 2.2
begin, end, for while, :=, if (utilizados na linguagem Pascal)
Exemplo 2.3 Os sı́mbolos: {, }, main, (, ), if, =, for, +, *, /, -, else,
case, switch, <, >, == são utilizados para construir a sintaxe da linguagem C,
C++ e C#.
33
34
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Definição 2.2 Alfabeto
Um alfabeto é um conjunto finito e não vazio de elementos chamados de sı́mbolos.
Convencionalmente, é utilizado a letra grega Sigma Σ para denotar um alfabeto.
Exemplo 2.4
Σ = {0, 1} é o chamado alfabeto binário.
Exemplo 2.5
português.
Σ = {a, b, c, . . . , x, y, z}, denota o conjunto de letras minúsculas do
Exemplo 2.6
Σ = {α, β, γ, δ, , ζ, η, θ, ι, λ, µ, π, ρ, σ, φ, ϕ, ψ, ...∆, Γ, Θ, Ψ, Ω, Σ, Υ},
representa o alfabeto grego.
Exemplo 2.7 Σ = {char, int, long, float, return, break, switch, if, else, <, ≤, =, ...}
é o alfabeto da linguagem de programação C.
Exemplo 2.8 Σ = { character, integer, real, do, while, for, continue, .ge., .le., ...}
é o alfabeto da linguagem de programação FORTRAN.
Definição 2.3 Palavra, string, cadeia
Uma palavra (cadeia ou string) sobre um conjunto (alfabeto) X é uma seqüência
finita de elementos de X.1
Exemplo 2.9 Com o conjunto: X = {a, b, c} podemos construir as seguintes palavras: s1 = aabc s2 = ababcc s3 = aabbcc s4 = cabaab
Exemplo 2.10
Dado o conjunto: Y = {1, 2, ∗} podemos construir os seguintes
strings: s1 = 112 ∗ 1 s2 = 2 ∗ 2 ∗ 1 s3 = ∗111 s4 = 1 ∗ ∗ ∗ 2 ∗ 1 ∗ ∗ ∗ 11
O alfabeto de uma linguagem natural (Português, Inglês, Espanhol, etc.) é
formado por palavras consideradas como objetos indivisı́veis e qualquer palavra da
linguagem corresponde a um sı́mbolo do alfabeto definido acima. Por exemplo, a
palavra computador é um objeto que não pode ser dividida em comput e ador, por
exemplo. Em contextos diferentes, podemos considerar dois alfabetos para a lingua
portuguesa: um, formado pelos caracteres P1 = {a, A, b, B, c, C, d, D, ..., z, Z} e,
outro P2, formado por todas as palavras encontradas em qualquer dicionário de
português, a partir das quais formaremos as ”palavras”ou frases em português. Os
strings leche, libro, cuaderno, mesmo sendo construı́dos a partir do alfabeto P1, não
fazem parte do Português.
Analogamente, o alfabeto de uma linguagem de programação é formada por um
conjunto de palavras-chave, variáveis e sı́mbolos da linguagem. Uma string desta
linguagem é uma seqüência de código-fonte. Assim, cada palavra-chave de uma linguagem de programação qualquer é um sı́mbolo do respectivo alfabeto. Por exemplo,
o segmento de programa Pascal:
1
Observação. Neste texto utilizaremos os termos string ou palavra indistintamente para indicar
o mesmo conceito.
35
2.1. PALAVRAS
Begin
x := 4 ;
End
ou
Begin
x:=4;
End
é uma palavra formada por seis sı́mbolos, Begin, x, := , 4, ; (ponto e vı́rgula)
e End. Os sı́mbolos B, e, g, i, n (do termo Begin) não são elementos do alfabeto
da linguagem de programação Pascal.
Convencionalmente e considerando a indivisibilidade dos elementos do alfabeto
de uma linguagem, os sı́mbolos são denotados por simples caracteres do inı́cio do
alfabeto português: a, b, c, d, e, ..., enquanto que, as palavras ou strings sobre um
alfabeto são representados pelos caracteres do final do alfabeto português: ..., p, q,
r, s, t, u, v, w, x, y, z, porém, nada impede que um sı́mbolo seja representado pelo
caractere x e uma palavra pelo caractere a.
Exemplo 2.11 alfabeto: Σ = {a, b, d}
strings:
x = abaa
u = bbdd
w = dada
Neste texto usaremos um string especial que não tem sı́mbolos, chamado de
string nulo (cadeia vazia, palavra nula ou palavra vazia) e denotado pelo sı́mbolo
λ (lambda minúsculo).
Definição 2.4 Conjunto de palavras
Seja Σ um alfabeto. O conjunto de palavras ou strings sobre o alfabeto Σ, e
denotado por Σ∗ , é definido recursivamente como segue:
• Base: λ ∈ Σ∗
• Passo Recursivo: Se w ∈ Σ∗ e a ∈ Σ, então wa ∈ Σ∗
• Fecho: w ∈ Σ∗ somente se pode ser obtido a partir de λ por um número finito
de aplicações do passo recursivo.
Para qualquer alfabeto não vazio Σ, o conjunto Σ∗ contém infinitos elementos.
Exemplo 2.12
Se Σ = {a}, então Σ∗ contém as palavras λ, a, aa, aaa, aaaa, ....
Exemplo 2.13
Σ = {a, b}, Σ∗ = {λ, a, b, aa, bb, ab, ba, aaa, bbb, aba, bab, ...}.
Exemplo 2.14
Σ = {0, 1}, Σ∗ = {λ, 0, 1, 00, 11, 01, 10, 0001, 101110, ...}
Exemplo 2.15
Se Σ = {a, b, c}, então {a, b, c}∗ = {λ, a, b, c, ab, ac, bc, ba, ca, abc, ...}
Exemplo 2.16
Se A = {♣, ♠} então A∗ = {λ, ♣, ♠, ♣♠, ♣♣, ♠♠, ♣♠♣, ...}
Resumindo:
• Se a ∈ Σ ⇒ a é um sı́mbolo
• Se w ∈ Σ∗ ⇒ w é uma palavra
36
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
2.1.1
Operações com palavras
Sejam w, u e v palavras sobre um determinado alfabeto Σ, então as seguintes
operações são realizadas com palavras w, u e v:
• Concatenação:
Se u = a1 a2 a3 . . . an e v = b1 b2 b3 . . . bm então u e v podem ser concatenados
para formar a palavra w da forma w = uv = a1 a2 a3 . . . an b1 b2 b3 . . . bm . A
palavra vazia λ é a identidade sob a concatenação, isto é, λw = wλ = w, para
qualquer palavra w
Exemplo 2.17
Se Σ = {a, b} e u = abb, v = aab então w = uv = abbaab e
z = vu = aababb
(Definiç~
ao recursiva) Seja u, v ∈ Σ∗ . A concatenação de u e v, escrito
como uv, é uma operação binária sobre Σ∗ , definido como segue:
◦ Base: Se |v = 0, então v = λ e uv = u
◦ Passo Recursivo: Seja v uma palavra com |v| = n > 0. Então v = wa,
para alguma palavra w com comprimento n − 1 e a ∈ Σ, e uv = (uw)a.
Exemplo 2.18
Seja u = ab, v = ca, e w = bb, então:
uv = abca
vw = cabb
(uv)w = abcabb
u(vw) = abcabb
Observações:
- a concatenação de palavras é uma operação binária associativa
- a concatenação de palavras não é comutativa uw 6= wu
- se u é uma palavra, então uu pode ser escrito como u2 , uuu = u3 ,
e também u0 = λ
• Reverso:
Se w = a1 a2 a3 . . . an então a palavra reversa ou o reverso de w é definido
por wR = an . . . a3 a2 a1
Exemplo 2.19
Se Σ = {0, 1} e w = 001011 então wR = 110100
(Definiç~
ao recursiva) Seja u uma palavra em Σ∗ . O reverso de u, denotado
por uR , é definido como segue:
◦ Base: |u| = 0. Então u = λ e λR = λ
◦ Passo Recursivo: Se |u| = n > 0, então u = wa para alguma palavra w
com tamanho n − 1 e algum a ∈ Σ, e uR = awR .
Exemplo 2.20
u = 01121, |u| = 5 > 0, então u = wa para w = 0112 com
|w| = 4, wR = 2110 e a = 1. Agora, uR = awR = 12110
Propriedades
37
2.1. PALAVRAS
◦ (wR )R = w para qualquer palavra w
◦ Se u, v ∈ Σ∗ , então (uv)R = v R uR
◦ Se v é uma subpalavra de w, então v R é uma subpalavra de wR
◦ (wn )R = (wR )n para qualquer palavra w e n ≥ 0.
◦ Um palı́ndromo sobre um alfabeto Σ é uma palavra em Σ∗ que têm
a mesma leitura da esquerda para direita e vice-versa. O conjunto de
palı́ndromos é o conjunto
{w ∈ Σ∗ /w = wR }
Exemplo 2.21 Sem considerar os espaços em branco:
’socorra me em marrocos’, ’subi no onibus’
Exemplo 2.22 Outros palı́ndromos: ana, arara, ovo, reviver, radar, asa,
123321, a1*1a
• Comprimento:
O comprimento ou tamanho de uma palavra w, denotada por length(w)
ou |w| é o número de elementos (sı́mbolos) da palavra, ou formalmente, é o
número de aplicações do passo recursivo para construir a palavra a partir dos
elementos do alfabeto.
◦ O comprimento da palavra λ é zero, i.é., |λ| = 0
◦ |a| = 1 se a ∈ Σ
◦ |wa| = |w| + 1
◦ |uv| = |u| + |v|
Exemplo 2.23
palavras:
comprimento
comprimento
comprimento
comprimento
Seja Σ = {a, b, c}. Os elementos de Σ∗ incluem as seguintes
0:
1:
2:
3:
λ
a b c
aa ab ac ba
aaa aab aac
baa bab bac
caa cab cac
bb bc ca cb cc
aba abb abc aca acb acc
bba bbb bbc bca bcb bcc
cba cbc cca ccb ccc
Definição 2.5 Subpalavra
u ∈ Σ∗ é uma subpalavra ou substring de v, se existem palavras x, y ∈ Σ∗ tal que
v = xuy.
Definição 2.6 prefixo, sufixo
Sejam w, u e v palavras sobre um determinado alfabeto Σ. Se w = uv então a palavra
u é chamada de prefixo de w, e a palavra v é chamada de sufixo da palavra w.
38
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 2.24 Caso Trivial : a palavra nula λ é prefixo e sufixo de qualquer palavra
w, pois, w = λw e também w = wλ.
Exemplo 2.25 Se Σ = {0, 1} e w = 100101011 então u = 1001 é um prefixo de w e
também v = 011 é um sufixo de w.
Exemplo 2.26
Se Σ = {a, b} e w = aababb então todos os prefixos de w são:
λ, a, aa, aab, aaba, aabab e aababb. Da mesma forma, todos os sufixos de w são:
b, bb, abb, babb, ababb e aababb
2.2
Linguagens
Definição 2.7 Linguagem formal
Uma linguagem formal L, ou simplesmente linguagem L, sobre um alfabeto Σ é
um sub-conjunto de Σ∗ . Se Σ é um alfabeto e L ⊆ Σ∗ , então dizemos que L é uma
linguagem sobre Σ.
Figura 2.1: Linguagens como subconjunto de palavras
Exemplo 2.27 Se Σ = {0, 1} então os conjuntos A= {00, 11} e B= {0, 1, 00, 11, 01, 10}
são duas linguagens, pois A⊆ Σ e B⊆ Σ.
Exemplo 2.28
Os casos triviais: Σ, ∅, Σ∗ são linguagens sobre o alfabeto Σ
Exemplo 2.29
Seja A ={a, b}. Os seguintes conjuntos são linguagens definidas
sobre o conjunto A:
• L1 = {a, ab, ab2 , ab3 , ...}: todas as palavras começando com o sı́mbolo a e
seguida por zero ou mais sı́mbolos b’s.
• L2 = {am bm |m > 0}: todas as palavras começando com um ou mais sı́mbolos
a’s seguida pelo mesmo número de sı́mbolos b’s.
• L3 = {bm abn |m ≥ 0, n ≥ 0}: todas as palavras com exatamente uma letra a.
• L4 = {0, 1}∗ {101}{0, 1}∗ : todas as palavras sobre {0,1}que contém a subpalavra 101
39
2.2. LINGUAGENS
• L5 = {w ∈ {a, b, c}/|w| ≤ 3} : conjunto de palavras sobre o alfabeto {a, b, c}
com comprimento menor ou igual a 3.
• L6 = {a, b}∗ ab{a, b}∗ ∪ {a, b}∗ ba{a, b}∗ : conjunto de palavras que contém a
subpalavra ab ou a subpalavra ba.
• L= {x, y}∗ : conjunto de todas as palavras sobre o alfabeto {x, y}
Lp = {xx, yy, xy, yx}∗ : conjunto de palavras sobre {x, y} de comprimento par
Li = {x, y}∗ − {xx, yy, xy, yx}∗ : conjunto de palavras sobre {x, y} de comprimento ı́mpar
2.2.1
Especificação de Linguagens
As linguagens de interesse para Ciência da Computação são aquelas onde as palavras
tem formas especificadas convenientemente. Formas aceitáveis definem a sintaxe da
linguagem (a maneira como são construı́das as palavras).
Para especificar (descrever) uma linguagem necessitamos de uma descrição precisa (não ambı́gua, não confusa) das palavras que compõem tal linguagem. Considerando que uma linguagem formal é um conjunto de palavras, então podemos
especificar as linguagens das seguintes formas:
• Por extensão: Uma linguagem finita pode ser explicitamente definida pela
enumeração (listagem) dos seus elementos (todas as palavras da linguagem).
• Por compreensão : quando descrevemos a propriedade P de todas as palavras.
L = {w ∈ Σ∗ /w tem a propriedade P }
Este método de especificação é muito utilizado principalmente para linguagens
infinitas (na maioria dos casos).
• Recursivamente: Linguagens infinitas podem ser definidas recursivamente apresentando os requisitos sintáticos para construir as suas palavras utilizando uma
base, um passo recursivo (algoritmo de construção) e um fecho (relação que
exclui os não-elementos).
Exemplo 2.30
Se L é a linguagem sobre Σ = {♣, ♥} de todas as palavras com
comprimento menor ou igual a 2, então ela tem seis elementos:
L = {λ, ♣, ♥, ♣♣, ♣♥, ♥♥}
Exemplo 2.31 A linguagem LaPAR sobre o conjunto {1, 0} na qual cada palavra
começa com um número 1 e tem comprimento par, pode ser definido recursivamente
da seguinte maneira:
40
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• Base: 11, 10 ∈ LaPAR
• Passo Recursivo: Se u ∈LaPAR, então u10, u01, u00 ∈LaPAR
• Fecho: Uma palavra u ∈LaPAR somente se pode ser obtida a partir de elementos da base por um número finito de aplicações do passo recursivo.
LaPAR ={11, 10, 1110, 1010, 1101, 1001, 1100, 1000, ... }
Exemplo 2.32
A linguagem LaB definido sobre o conjunto {4, a} na qual cada
ocorrência de a é imediatamente precedida por um número 4 é especificada da seguinte forma:
• Base: λ ∈LaB.
• Passo Recursivo: Se u ∈LaB, então u4, u4a ∈LaB.
• Fecho: Uma palavra u ∈LaB somente se pode ser obtida a partir dos elementos
da base por um número finito de aplicações do passo recursivo.
São palavras da linguagem LaB: λ, 4, 4a, 4a444a. Não são palavras da linguagem
LaB: a, aa, a4, 4aa.
2.2.2
Operações sobre Linguagens
Definição 2.8 União
Se L1 e L2 são duas linguagens sobre o mesmo alfabeto então a união L1 ∪ L2 é uma
linguagem
L1 ∪ L2 = {w ∈ Σ∗ /w ∈ L1 ou w ∈ L2 }
Definição 2.9 De Morgan
Se L1 e L2 são duas linguagens sobre o mesmo alfabeto então,
(L1 ∪ L2 )c = Lc1 ∩ Lc2
(L1 ∩ L2 )c = Lc1 ∪ Lc2
Definição 2.10 concatenação
A concatenação das linguagens X e Y, denotado por XY, é a linguagem
XY = {uv|u ∈ X e v ∈ Y }
A concatenação de X consigo mesma n vezes é denotada por Xn . O conjunto X0 é
definido como {λ}
41
2.3. CONJUNTOS REGULARES
Exemplo 2.33
Sejam X = {a, b, c} e Y = {012, 02}. Então
XY = {a012, b012, c012, a02, b02, c02}
X0 = {λ}
= a palavra nula
1
X = {a, b, c}
= conjunto de palavras de tamanho 1
2
X = {aa, ab, ac, ba, bb, bc, ca, cb, cc}
= conjunto de palavras de tamanho 2
... = ...
Xn = {aaa...a, bbb...b, ..., abcabc..., ...}
= conjunto de palavras de tamanho n
= {w ∈ {a, b, c}∗ /|w| = n}
Definição 2.11 Estrela de Kleene
Seja X um conjunto qualquer de sı́mbolos. Então, a Estrela de Kleene do conjunto
X, denotado por X∗ , é definido como
∗
X =
∞
[
Xi = X0 ∪ X ∪ X2 ∪ · · · ∪ Xn ∪ · · ·
i=0
e
+
X =
∞
[
X i = XX ∗
i=1
∗
Observe que X é conjunto de todas as palavras sobre o conjunto X e
X ∗ = X + ∪ {λ}
Por exemplo, {a, b}∗ é conjunto de todas as palavras construı́das usando os sı́mbolos
a e b. Também, X+ é conjunto de palavras não nulas construı́das a partir do conjunto
X
2.3
Conjuntos Regulares
Informalmente podemos dizer que um conjunto é regular se ele pode ser gerado a
partir de um conjunto vazio, do conjunto que contém a palavra nula λ, de conjuntos
unitários contendo um sı́mbolo do alfabeto e utilizando apenas as operações de união,
concatenação e estrela de Kleene.
Definição 2.12 Conjunto regular
Seja Σ um alfabeto. Um conjunto regular sobre Σ é definido recursivamente como:
• Base: O conjunto vazio ∅, e os con juntos unitários {λ} e {a}, para cada
sı́mbolo a ∈ Σ, são conjuntos regulares sobre Σ
42
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• Passo Recursivo: Se X e Y são conjuntos regulares sobre Σ, então os conjuntos
X ∪ Y (união), XY (concatenação) e X∗ também são conjuntos regulares sobre
Σ.
• Fecho: X é um conjunto regular sobre Σ somente se este pode ser obtido partir
dos elementos da base por um número finito de aplicações do passo recursivo.
Exemplo 2.34
Seja Σ = {1, 2} então:
• {}, {λ}, {1}, {2} são conjuntos regulares sobre {1, 2}
• {1} ∪ {2} = {1, 2} é um conjunto regular sobre {1, 2}
• {1, 2}{2} = {12, 22} é um conjunto regular sobre {1, 2}
• {11, 12, 21, 22}, {1, 12, 122, 21, 1121, ...} são conjuntos regulares sobre {1, 2}
Exemplo 2.35 A linguagem L = {a, b}∗ {aba}{a, b}∗ , o conjunto de palavras contendo
a sub-palavra aba, é um conjunto regular sobre {a, b}
Exemplo 2.36 O conjunto de palavras que começam e terminam com 0 e contém
pelo menos um 1, é regular sobre {0, 1}. As palavras neste conjunto poderão ser
descritos intuitivamente como: “um 0, seguido por qualquer palavra, seguido por um
1, seguido por qualquer palavra, seguido por um 0”. A concatenação
{0}{0, 1}∗ {1}{0, 1}∗ {0} = ABCBA
mostra a regularidade do conjunto. Vejamos por que:
• 0 ∈ {0, 1} logo A = {0} é regular (Base)
• 0, 1 ∈ {0, 1} então A = {0} e C = {1} são regulares e também {0}∪{1} = {0, 1}
é regular (união, Passo Recursivo). Logo, B = {0, 1} também é regular (estrela
de Kleene, Passo Recursivo).
• Se A e B são regulares então AB é regular (concatenação, Passo Recursivo).
Sucessivamente aplicamos este fato para provar que (((AB)C)B)A é regular
2.4
Expressões Regulares
Definição 2.13 expressão regular
Expressões regulares são abreviações que denotam ou identificam conjuntos regulares
Exemplo 2.37
Se {a}, {b} são conjuntos regulares, então a,b são expressões regulares
2.4. EXPRESSÕES REGULARES
43
Se u = {a, b} então u é uma expressão regular
Se u = {a} e v = {aa, bb} então (u ∪ v) é uma expressão regular
Se {a, b}∗ é um conjunto regular então (a∪b)∗ é uma expressão regular
Definição 2.14 expressão regular
Seja Σ um alfabeto. Uma expressão regular sobre o alfabeto Σ é definida recursivamente como:
• Base: ∅, λ e a, para cada a ∈ Σ, são expressões regulares sobre Σ. Estas são
chamadas de expressões regulares primitivas
• Passo Recursivo: Se e1 e e2 são expressões regulares sobre Σ, então as expressões (e1 ∪ e2 ), (e1 e2 ) e (e∗1 ) são expressões regulares sobre Σ
• Fecho: u é uma expressão regular sobre Σ somente se pode ser obtido a partir
dos elementos da base por meio de um número finito de aplicações do passo
recursivo.
Exemplo 2.38
Se Σ = {0, 1, 2} então são expressões regulares: ∅, λ, 0, 1, 2
Exemplo 2.39 Se Σ = {m, n} então são expressões regulares: m, n, (m ∪ n), mn, (m∗ )
e (n∗ )
Exemplo 2.40 A expressão regular (0 ∪ 1)∗ 010(0 ∪ 1)∗ representa o conjunto regular das palavras que contém a subpalavra 010 (sobre o alfabeto {0, 1})
Definição 2.15 Expressão regular
Cada uma das seguintes é uma expressão regular sobre um alfabeto Σ:
• O sı́mbolo λ (palavra vazia) e o par ( ) (expressão vazia) são expressões regulares.
• Cada sı́mbolo a ∈ Σ é uma expressão regular.
• Se r é uma expressão regular, então (r∗ ) é uma expressão regular.
• Se r1 e r2 são expressões regulares, então (r1 ∨ r2 ) é uma expressão regular. O
sı́mbolo ∨ é o OU lógico.
• Se r1 e r2 são expressões regulares, então (r1 r2 ) é uma expressão regular.
Exemplo 2.41
Expressão Regular Conjunto regular
a, aa, aaa
{a}
ab, abab
{ab}
∗
(a ∪ b)
{a, b}∗
44
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Duas expressões que representam o mesmo conjunto são chamadas de equivalentes As identidades da tabela 2.1 [SUD 05] podem ser usadas para manipular
algebricamente expressões regulares para construir expressões equivalentes.
Tabela 2.1: Identidades de Expressões Regulares
1. ∅u = u∅ = ∅
2. λu = uλ = u
3. ∅∗ = λ
4. λ∗ = λ
5. u ∪ v = v ∪ u
6. u ∪ ∅ = u
7. u ∪ u = u
8. u∗ = (u∗ )∗
9. u(v ∪ w) = uv ∪ uw
10. (u ∪ v)w = uw ∪ vw
11. (uv)∗ u = u(vu)∗
12. (u ∪ v)∗ = (u∗ ∪ v)∗
= u∗ (u ∪ v)∗ = (u ∪ vu∗ )∗
= (u∗ v ∗ )∗ = u∗ (vu∗ )∗
= (u∗ v ∗ )u∗
Outras identidades interessantes:
a∗ ∅ = ∅, onde a é um sı́mbolo de um alfabeto
∅∗ = {λ}
r ∪ ∅ = r, onde r é uma expressão regular
rλ = r, r é uma expressão regular
Se Σ = {a, b} e r = a então L(r) = {a} e L(r ∪ λ) = {a, λ}
2.5
Linguagens Regulares
Definição 2.16 Linguagem sobre um alfabeto
A linguagem L(r) sobre o alfabeto A, definida pela expressão r sobre A, é definida
da seguinte forma:
1. L(λ) = {λ} e L(()) = ∅
2. L(a) = {a}, onde a é uma letra em A.
3. L(r∗ ) = (L(r))∗ , o fecho de Kleene
4. L(r1 ∨ r2 ) = L(r1 ) ∪ L(r2 ), união de linguagens
45
2.6. EXERCı́CIOS
5. L(r1 r2 ) = L(r1 )L(r2 ), concatenação de linguagens
Exemplo 2.42 Seja Σ = {x, y} e r = Σ∗ xΣ∗ então L(r) é o conjunto de palavras w
onde cada w tem pelo menos um sı́mbolo x
Exemplo 2.43 Seja Σ = {0, 1} e r = 1∗ (10+ )∗ então L(r) é o conjunto de palavras
w onde todo 1 em w é seguido por pelo menos um sı́mbolo 0.
Exemplo 2.44 Σ = {0, 1} e r = 0Σ∗ 0 ∪ 1Σ∗ 1 ∪ 0 ∪ 1, então L(r) é o conjunto de
palavras que começa e termina com o mesmo sı́mbolo.
Exemplo 2.45
Se Σ = {a, b} então para r = (a∪λ)(b∪λ) temos L(r) = {λ, a, b, ab}.
Definição 2.17 Linguagem regular
Seja L uma linguagem sobre A. Então L é chamada uma linguagem regular sobre
A se existe uma expressão regular r sobre A tal que L = L(r), isto é, todas as
linguagens regulares podem ser especificadas por expressões regulares
Exemplo 2.46
Seja A = {a, b}.
• r = a∗ , então L(r) consiste de todas as potências de a, incluindo a palavra
vazia λ
• r = aa∗ , então L(r) consiste de todas as potências positivas de a
• r = (a ∨ b)∗ . Note que L(a ∨ b) = {a} ∪ {b} = A. Logo L(r) = A∗ : toda as
palavras sobre A.
• r = a ∧ b∗ . Neste caso, L(r) não existe, pois r não é uma expressão regular.
2.6
Exercı́cios
1. Dar três exemplos de alfabetos conhecidos
2. Se Σ = {0, 1}, qual das afirmações é correta: 0 ∈ Σ ou 0 ∈ Σ∗ . Por que?
3. Provar por indução sobre i, que (wR )i = (wi )R para qualquer palavra w e para
todo i ≥ 0
4. Seja X = {aa, bb} e Y = {λ, b, ab}.
(a) Listar as palavras no conjunto XY.
(b) Listar as palavras do conjunto Y∗ de tamanho 3 ou menos
(c) Quantas palavras de tamanho 6 existem em X∗ ?
5. Seja A = {a, b}. Descreva verbalmente as seguintes linguagens sobre A:
46
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
(a) L1 = {(ab)m |m > 0}
(b) L2 = {ar bas bat |r, s, t ≥ 0}
(c) L3 = {a2 bm a3 |m > 0}
6. Considere a linguagem L = {ab, c} sobre A = {a, b, c}. Encontrar as linguagens
L0 , L3 e L−2 .
7. Dar uma expressão regular que represente o conjunto:
(a) de palavras sobre {1, 0} que contém as sub-palavras 11 e 10
(b) de palavras sobre {a, b} que contém as sub-palavras ab e ba
(c) de palavras sobre {a, b, c} de tamanho menor de três
(d) de palavras de tamanho ı́mpar sobre {a, b, c} que contém exatamente uma
a.
(e) de palavras sobre {a, b, c}, onde cada b é seguida imediatamente por pelo
menos um c.
(f) de palavras sobre {1, 2, 3} de comprimento ı́mpar
8. Encontre dois prefixos e dois sufixos para a palavra nomamin em {o, a, i, m, n}∗
9. Utilizando a definição recursiva, determine os reversos das palavras 00101 e
1011
10. Se u = 0101 e v = 10101, determine o reverso de uv e de vu sobre Σ = {0, 1}
11. Fazer uma lista de pelo menos 10 palı́ndromos conhecidos
12. Utilize a Tabela 2.1 para estabelecer as seguintes identidades:
(a) (ba)+ (a∗ b∗ ∪ a∗ ) = (ba)∗ ba+ (b∗ ∪ λ)
(b) b+ (a∗ b∗ ∪ λ)b = b(b∗ a∗ ∪ λ)b+
(c) (a ∪ b)∗ = (a ∪ b)∗ b∗
(d) (a ∪ b)∗ = (a∗ ∪ ba∗ )∗
(e) (a ∪ b)∗ = (b∗ (a ∪ λ)b∗ )∗
13. Para um dos alfabetos seguintes escrever pelo menos cinco conjuntos regulares
(a) Σ = {x, y, z}
(b) Σ = {5, 7, 9}
(c) Σ = {café, com, leite, pão, açúcar}
(d) Σ = {x, y, =, <, 1, 4}
2.6. EXERCı́CIOS
47
14. Suponha que Σ = {0, 1}. Escreva expressões regulares para os seguintes conjuntos:
(a) Todas as palavras em Σ∗ com não mais que três 0’s .
(b) Todas as palavras em Σ∗ com um número de 1’s divisı́veis por três.
(c) Todas as palavras em Σ∗ com, exatamente, uma ocorrência da sub-palavra
000.
15. Quais das seguintes afirmações são verdadeiras? Justifique sua resposta.
(a) baa ∈ a∗ b∗ a∗ b∗
(b) b∗ a∗ ∩ a∗ b∗ = a∗ ∪ b∗
(c) abcd ∈ (a(cd)∗ b)∗
16. Para r = ab ∪ ba, determinar L(r)
17. Se r = (ΣΣ)∗ , onde Σ é um alfabeto, determinar L(r)
48
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Capı́tulo 3
Autômatos Finitos
Um autômato, tal como é estudado na disciplina de Teoria da Computação, é um
modelo matemático computacional, isto é, descreve em forma abstrata o comportamento de um computador.
Um procedimento ou atividade real que determina quando uma palavra é parte
de uma linguagem é chamado aceitante de linguagem. O objetivo deste capı́tulo,
é definir uma classe de máquinas abstratas (independente de sua implementação)
cujas computações determinem a aceitabilidade de uma palavra de entrada, isto
é, apresentar um modelo matemático de computador (máquina computacional) que
aceite uma entrada, processe esta entrada, e gere uma saı́da para esta entrada. Para
cada entrada, a máquina abstrata terá um determinado comportamento (processo).
Os autômatos finitos ao modelar uma máquina abstrata computacional, mostra
o QUE faz esta máquina (processamento, compilação, simulação).
Figura 3.1: Máquina Abstrata
Estados da máquina são ”fotografias”(snapshots, E1 , E2 , ..., En ) mostrando o
comportamento da máquina em um determinado momento. O processamento de
uma tarefa através de uma máquina é a seqüência (histórico) de estados E1 , E2 , ...,
En , começando pelo estado inicial E1 e terminando no estado final En .
Por exemplo, uma máquina de vender bebidas (drink machine), aceita uma mo49
50
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
eda ou ficha como entrada e devolve uma bebida como saı́da.
• Um estado inicial: a máquina com a lata de bebida no seu interior pronta para
ser oferecida, e o usuário com a moeda adequada pronta para ser introduzida
na máquina.
• O processamento da entrada: a máquina verificando se a moeda ou ficha corresponde ao valor do produto selecionado
• Um estado final: o usuário com a lata de bebida desejada na mão e a moeda
introduzida na máquina.
Figura 3.2: Máquina de vender bebidas
3.1
Uma ferramenta: JFLAP
JFLAP (http://www.jflap.org/) é um pacote de ferramentas gráficas desenvolvidas
por Susan H. Rodger ([email protected]) no Departamento de Ciência da Computação da Duke University, NC, USA. JFLAP é um software de distribuição gratuita para testes com tópicos de linguagens formais: autômatos finitos não-determinı́sticos,
autômatos de pilha não-determinı́sticos, máquinas de Turing multi-fita e vários tipos
de gramáticas.
As principais caracterı́sticas do JFLAP (versão 7.0, em 17/01/2011) incluem:
3.1. UMA FERRAMENTA: JFLAP
51
• Interface agradável para Windows e Macintoch
• Construção de autômatos finitos e de pilha
• Construção de tabelas para LL e LR
• Analisadores para gramáticas
• Máquinas Mealy e Moore
• Transformação de CGF (Context-Free Grammar) em CNF (Chomsky Normal
Form)
• Algoritmos para converter AEF em expressões regulares
• Comparação de dois AEF (equivalência)
JFLAP 7.0 requer a presença do compilador Java 1.5 ou superior. O texto de
referência sobre o JFLAP é [ROD 06]
Figura 3.3: JFLAP - Conteúdo Menu Principal (v.7.0)
52
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Figura 3.4: JFLAP - Editor de Autômatos e Entrada de dados
Figura 3.5: Simulações com JFLAP
3.2
Autômatos Finitos Determinı́sticos
Informalmente, podemos afirmar que um autômato é um modelo abstrato (sem detalhes) de um computador digital. Algumas caracterı́sticas de um autômato padrão
incluem:
• Uma entrada
• Uma saı́da
53
3.2. AUTÔMATOS FINITOS DETERMINı́STICOS
• um dispositivo de armazenagem
• Uma unidade de controle
• Um conjunto de estados internos da máquina
Definição 3.1 Autômato Finito Determinı́stico, AFD
Um Autômato Finito Determinı́stico (AFD) chamado também de Aceitante
Finito Deterministico ou Reconhecedor de sı́mbolos, é uma máquina abstrata definida
como uma tupla (5-upla)
M = (Q, Σ, δ, q0 , F )
onde
Q = {q0 , q1 , . . . , qn } é o conjunto de finito de estados internos da
máquina
Σ é um alfabeto (conjunto de sı́mbolos)
q0 ∈ Q é o estado inicial
F ⊂ Q é o conjunto de estados finais ou aceitos
δ : Q × Σ −→ Q é uma função total chamada função de transição
Exemplo 3.1 A máquina M definida como M = (K, Σ, s, F ) é um autômato finito
determinı́stico onde
K = {q0 , q1 },
Σ = {a, b},
s = q0 ,
F = {q0 }
e onde δ : K × Σ → K é a função de transição definida como:
δ(q0 , a) = q0
δ(q0 , b) = q1
δ(q1 , a) = q1
δ(q1 , b) = q0
e mostrada no grafo da Fig. 3.6
b
a
q1
q0
a
b
Figura 3.6: Autômato Finito Determinı́stico
Para entender a sua natureza mecânica, a operação de um AFD é descrita em
termos de componentes que estão presentes em muitas máquinas de computação:
54
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
a
b
a
b
Fita de entrada
cabeça de leitura
q0
controle finito
Figura 3.7: Autômato
um registrador interno simples, um conjunto de valores para o registrador, uma fita,
um leitor de fitas, e um conjunto de instruções.
• Os estados de um AFD representam o status interno da máquina.
• O registrador da máquina, chamado de controle interno ou unidade de controle,
contém o estado corrente da máquina. No inı́cio da computação, contém o
estado inicial q0 .
P
• A entrada é uma seqüência finita de elementos obtidos do alfabeto .
• A fita armazena as entradas a serem computadas, e é dividida em quadrados.
Cada quadrado com a capacidade de conter um elemento do alfabeto. A
fita deve ter comprimento ilimitado. A entrada para uma computação pelo
autômato é colocado no segmento inicial da fita
• A cabeça da fita lê um quadrado da fita de entrada.
• O corpo da máquina consiste da cabeça da fita e do registrador
• A posição da cabeça de fita é indicado colocando a cabeça da fita sob o quadrado que esta sendo explorada.
• O estado corrente do autômato é indicado pelo valor do registrador.
• A configuração inicial de uma computação com entrada baba é representada
pela Fig. 3.7
• O estado da máquina e o sı́mbolo explorado determinam a instrução a ser executada. A ação de uma máquina em estado qi explorando (executando,processando)
um único sı́mbolo a e produzir um novo estado, δ(qi , a) no controle. Considerando que δ é uma função total, existe exatamente uma instrução especificada
para cada combinação de estado e sı́mbolo de entrada (determinismo).
• O conjunto de instruções (programa) é construı́do a partir da função de transição
δ do AFD.
55
3.2. AUTÔMATOS FINITOS DETERMINı́STICOS
• A computação de um autômato é a execução de uma seqüência de instruções.
A execução de uma instrução altera o estado da máquina e move a cabeça da
fita um quadrado à direita.
• O status da máquina em qualquer momento da computação é chamado
P de
configuração. Esta configuração é qualquer elemento do conjunto Q × ∗ .
configuração = ( estado , palavra )
Por exemplo, na segunda computação da máquina mostrada na Fig. 3.8, a
configuração é (q1 , ba).
O objetivo de uma computação por parte de um autômato é determinar a aceptabilidade de uma cadeia de caracteres de entrada, por exemplo, ”a := x + Y”.
Uma computação começa com a cabeça da fita explorando o quadrado mais a
esquerda da fita e o registrador contendo o estado inicial q0 . O estado e a instrução
são usados para selecionar a instrução. A máquina então altera seu estado como
indicado pelo programa e a cabeça da fita move-se a direita. O ciclo da instrução é
repetido até a cabeça da fita ficar num quadrado em branco (palavra vazia, λ).
Definição 3.2 Função de Transição Estendida, δ ∗
A função de transição δ que processa um único sı́mbolo do alfabeto Σ, pode ser
estendida, δ ∗ , para processar uma única palavra, utilizando a definição recursiva
seguinte:
δ ∗ : Q × Σ∗ −→ Q
• Base: δ ∗ (q, λ) = q, para todo q ∈Q
• Passo recursivo: δ ∗ (q, wa) = δ(δ ∗ (q, w), a), para todo q ∈Q, w ∈ Σ∗ , a ∈ Σ
Exemplo 3.2 Se Q = {q0 , q1 }, Σ = {a, b}, s = q0 ,
função de transição definida como:
δ(q0 , a) = q0
δ(q0 , b) = q1
δ(q1 , a) = q1
δ(q1 , b) = q0
então:
δ ∗ (q0 , abb) = δ(δ ∗ (q0 , ab), b)
= δ(δ(δ ∗ (q0 , λa), b), b)
= δ(δ(δ(δ ∗ (q0 , λ), a), b), b)
= δ(δ(δ(q0 , a), b), b)
= δ(δ(q0 , b), b)
= δ(q1 , b)
= q0
F = {q0 } e δ : K × Σ → K é a
(Passo recursivo)
(a = λa
(Base)
Definição 3.3 Palavra aceita por uma máquina
Uma palavra de entrada é aceita por uma máquina abstrata M, se a computação de
56
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
a
b
a
q0
a
b
a
b
q1
a
b
a
q0
q0
a
b
b
a
a
q1
q1
a
Figura 3.8: Computação na máquina M2
M termina em um estado aceitável, isto é, em um estado que faz parte do conjunto
de estados finais. Caso contrário, a palavra é rejeitada por M.
Exemplo 3.3
A máquina M2 definida como:
M2:
Q = {q0 , q1 }
Σ = {a, b}
F = {q1 }
δ(q0 , a) = q1
δ(q0 , b) = q0
δ(q1 , a) = q1
δ(q1 , b) = q0
aceita a palavra aba como mostra a Fig. 3.8
Definição 3.4 Linguagem de uma máquina
Seja M = (Q, Σ, δ, q0 , F ) um autômato finito determinı́stico. A linguagem de M,
57
3.2. AUTÔMATOS FINITOS DETERMINı́STICOS
denotada por L(M), é o conjunto de palavras em Σ∗ aceitas por M.
L(M ) = {x ∈ Σ∗ |x é aceita por M }
= {x ∈ Σ∗ |δ ∗ (q0 , w) ∈ F }
Definição 3.5 Máquinas equivalentes
Duas máquinas que aceitam a mesma linguagem são ditas ser equivalentes.
Definição 3.6 `M
A relação binária `M sobre Q ×Σ+ , definida por
(qi , aw) `M (δ(qi , a), w)
para cada a ∈ Σ e w ∈ Σ∗ , se aplica entre duas configurações de M, se, e somente
se, a máquina pode passar da configuração (qi , aw) para a configuração (δ(qi , a), w)
como resultado ou através de um simples movimento (da cabeça da fita). Neste caso
dizemos que (qi , aw) produz um resultado (δ(qi , a), w) em um passo.
A notação
(qi , u) `∗ (qj , v)
é usada para indicar que a configuração (qj , v) pode ser obtida de (qi , u) por zero ou
mais transições.
Exemplo 3.4
F), onde
Suponhamos que M3 seja o autômato finito determinı́stico (Q, Σ, δ, q0 ,
M3:
Q = {q0 , q1 }
Σ = {0, 1}
F = {q0 }
δ(q0 , 0) = q0
δ(q0 , 1) = q1
δ(q1 , 0) = q1
δ(q1 , 1) = q0
Podemos verificar que a linguagem L(M3) é o conjunto de palavras em {0, 1}∗ que
têm um número par de 1’s. Consideremos a palavra de entrada 00110, sua configuração inicial é (q0 , 00110). Então:
(q0 , 00110) `M
`M
`M
`M
`M
(q0 , 0110)
(q0 , 110)
(q0 , 10)
(q0 , 0)
(q0 , λ)
Portanto, q0 , 00110) `M (q0 , λ) , e assim 00110 é aceita pela máquina M3, pois q0 é
um estado final.
Exemplo 3.5 No exemplo anterior da máquina M3, consideremos a palavra 01011
(com um número ı́mpar de 1’s)
58
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
(q0 , 01011) `M
`M
`M
`M
`M
(q0 , 101)
(q1 , 011)
(q1 , 11)
(q0 , 1)
(q1 , λ)
Observamos que q1 6∈ F (não é um estado final), logo a palavra 01011 é rejeitada
pela linguagem L(M3).
Definição 3.7 Diagrama de estados
O diagrama de estados de um autômato finito determinı́stico M = (Q, Σ, δ, q0 ,
F) é um grafo rotulado G definido pelas seguintes condições
1. Os vértices de G são os elementos de Q.
2. Os rótulos sobre as arestas (arcos) de G são elementos do alfabeto
P
.
3. q0 é o vértice (nodo) inicial.
4. F é o conjunto de nodos de aceitação.
5. Existe uma aresta do nodo qi até o nodo qj rotulado com a, se δ(qi , a) = qj .
6. Para cada nodo qi e sı́mbolo a ∈ Σ, existe exatamente uma aresta rotulada
com a deixando qi .
Exemplo 3.6
M4:
Q = {q0 , q1 , q2 , q3 }
Σ = {0, 1}
F = {q0 , q1 , q2 }
O diagrama de estados é mostrado na Fig. 3.9.
δ(q0 , 0) = q0
δ(q0 , 1) = q1
δ(q1 , 0) = q0
δ(q1 , 1) = q2
δ(q2 , 0) = q0
δ(q2 , 1) = q3
δ(q3 , 0) = q3
δ(q3 , 1) = q3
59
3.3. AUTÔMATOS FINITOS NÃO-DETERMINı́STICOS
0
1
0
q0
1
q1
1
q2
1
0
q3
0
Figura 3.9: Diagrama de estados para um AFD
3.3
Autômatos Finitos Não-Determinı́sticos
Definição 3.8 Autômato Finito Não-Determinı́stico, AFND
Um Autômato Finito Não-Determinı́stico (AFND) é uma tupla (5-upla)
M = (Q, Σ, δ, q0 , F )
onde
Q
P é o conjunto de finito de estados
é um alfabeto
q0 ∈ Q é o estado inicial
F ⊂ Q é o conjunto de estados finais ou aceitos
δ é uma função total de Q×Σ para P(Q) chamada função de transição.
P(Q) é o conjunto de partes (conjunto de conjuntos) de Q.
A única diferença entre um AFD e um AFND, está na função de transição. Neste
último, as saı́das (os ”próximos estados”) podem ser zero, um ou mais
a
qn
qi
qi
δ(qn,a) ={qi}
qn
qn
δ(qn,a) ={ }
a
a
a
δ (qn,a) ={qi , qj, qk}
qj
qk
Figura 3.10: Autômato Finito Não-determinı́stico
60
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 3.7
A máquina N definida como:
N:
Q = {q0 , q1 , q2 }
Σ = {a, b}
F = {q2 }
δ(q0 , a)
δ(q0 , b)
δ(q1 , a)
δ(q1 , b)
δ(q2 , a)
δ(q2 , b)
=
=
=
=
=
=
{q0 }
{q0 , q1 }
∅
{q2 }
∅
∅
é um autômato finito não-determinı́stico, que aceita a computação da palavra ababb
(q0 , ababb)
`N (q0 , babb)
`N (q0 , abb)
`N (q0 , bb)
`N (q0 , b)
`N (q0 , λ)
(q0 , ababb)
(q0 , ababb)
`N (q0 , babb)
`N (q0 , babb)
`N (q1 , abb)
`N (q0 , abb)
`N (q0 , bb)
`N (q1 , b)
`N (q2 , λ)
A segunda computação da máquina N finaliza depois da execução de três instruções,
pois nenhuma ação é especificada quando a máquina N está no estado q1 explorando
o sı́mbolo a
Definição 3.9 Palavra aceita
Uma palavra de entrada w é aceita pela máquina N se existe pelo menos uma
computação que processa a palavra completa w e parar em um estado aceitável
(final). Uma palavra é um elemento de uma linguagem de uma máquina nãodeterminı́stica, se existe uma computação que aceita esta palavra.
Definição 3.10 Linguagem de um autômato
A linguagem de um autômato finito não-determinı́stico N, denotado por L(N), é o
conjunto de palavras aceitas por N, isto é,
L(N) = {w|∃(q0 , w) `∗ (qi , λ) com qi ∈ F}
q0
b
q1
b
a, b
Figura 3.11: Grafo do autômato N
q2
61
3.4. AUTÔMATOS FINITOS E EXPRESSÕES REGULARES
Podemos observar graficamente que a linguagem aceita por N é (a ∪ b)∗ bb
Exemplo 3.8
Seja a máquina N2 = (Q, Σ, δ, s, F) onde:
Q = {q0 , q1 , q2 , q3 , q4 }
Σ = {a, b}
F = {q4 }
s = q0
δ(q0 , a)
δ(q0 , b)
δ(q1 , a)
δ(q1 , b)
δ(q2 , λ)
δ(q3 , b)
δ(q4 , a)
δ(q4 , b)
=
=
=
=
=
=
=
=
{q0 }
{q0 , q1 }
q3
{q2 }
q4
q4
q4
q4
Na Fig. 3.12 podemos observar que este é um dos vários possı́veis autômatos finitos não-determinı́sticos que aceitam o conjunto de palavras contendo uma ocorrência
do padrão bb ou do padrão bab
a, b
q0
b
q1
q2
b
λ
a
a, b
q3
b
q4
Figura 3.12: Autômato Não-Determinı́stico N2
Executando as respectivas computações podemos afirmar que a palavra bababab
é aceita pela linguagem L(N2).
3.4
Autômatos Finitos e Expressões Regulares
Teorema 3.1. A classe de linguagens aceita por autômatos finitos é fechada sob
união, concatenação, estrela de Kleene, complementação e intersecção.
Prova.- ver [LEW 00].
62
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
a, b
M1:
q 1,0
a, b
q 1,1
b
q1,2
b
b
a
M2:
q2,0
q2,1
b
Figura 3.13: Autômatos Não-Determinı́sticos M1 e M2
Teorema 3.2. Uma linguagem é regular se e somente se ela é aceita por um
autômato finito.
3.5
Transições Lambda
As transições de um estado para outro nos autômatos determinı́sticos e não-determinı́sticos
são inicializados pelo processamento de um sı́mbolo de entrada. Nos AFND, permitese as transições de estado sem a necessidade de processar uma entrada. Esta
transição é chamada de transição lambda. Os autômatos que utilizam este tipo
de transições são denotados por AFND-λ.
Definição 3.11 Autômato com transições lambda
Um P
autômato finito não-determinı́stico com transições lambda é uma tupla NL =
{Q, , δ, q0 , F}, onde Q, q0 e F são os mesmos de um AFND. A função de transição
é definida como:
X
δ :Q×(
∪{λ})P(Q).
Diagramas de estado para um AFND-λ é construı́do utilizando transições lambda
com arcos rotulados com o sı́mbolo λ.
Transições lambda podem ser usadas para construir máquinas complexas a partir
de máquinas mais simples.
Exemplo 3.9
Sejam M1 e M2 duas máquinas como mostra a Fig. 3.13 e que
aceitam, respectivamente, a ∪ b)∗ bb(a ∪ b)∗ e (b ∪ ab)∗ (a ∪ λ). Os estados finais são,
respectivamente, F1 = {q1,2 } e F2 = {q2,0 , q2,1 }.
A linguagem do AFND-λ é L(M1) ∪ L(M2).
63
3.6. EQUIVALÊNCIA DE AUTÔMATOS
a, b
a, b
M:
λ
q0
q 1,0
b
λ
b
q 1,1
b
q1,2
a
q2,0
q 2,1
b
Figura 3.14: Autômato Não-Determinı́stico Composto
A computação na máquina composta M (Fig. 3.14) começa no estado q0 e segue
uma aresta lambda ao estado inicial de M1 ou M2.
Se o caminho p mostra a aceitação da palavra pela máquina Mi , i = 1, 2, então
a palavra é aceita pela máquina M. Desde que, o movimento inicial (de q0 a qi,0 )
em cada computação não processa qualquer sı́mbolo de entrada, a linguagem de M
é L(M1) ∪ L(M2)
3.6
Equivalência de autômatos
Definição 3.12 Autômatos Equivalentes
Dois autômatos finitos M1 e M2 são equivalentes, e escrevemos M1 ≡ M2, se L(M1)
= L(M2), isto é, se ambos autômatos aceitam a mesma linguagem.
3.7
Exercı́cios
1. Mostrar o grafo dos seguintes Autômatos Finito Determinı́sticos:
Q={q0 , q1 , q2 , q3 }
Σ = {0, 1}
(a)
s = q0
F= {q3 }
δ(q0 , 0) = q2
δ(q0 , 1) = q1
δ(q1 , 0) = q2
δ(q1 , 1) = q1
δ(q2 , 0) = q3
δ(q2 , 1) = q2
δ(q3 , 0) = q3
δ(q3 , 1) = q2
64
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Q={q0 , q1 , q2 , q3 , q4 }
Σ = {0, 1}
(b) s = q0
F= {q2 , q4 }
δ(q0 , 0) = q1
δ(q0 , 1) = q3
δ(q1 , 0) = q2
δ(q1 , 1) = q4
δ(q4 , 0) = q4
δ(q2 , 0) = q1
δ(q2 , 1) = q4
δ(q3 , 0) = q2
δ(q3 , 1) = q4
δ(q4 , 1) = q4
Q={q0 , q1 , q2 , q3 , q4 }
Σ = {x, y}
(c) s = q0
F= {q4 }
δ(q0 , x) = q1
δ(q0 , y) = q0
δ(q1 , x) = q2
δ(q1 , y) = q3
δ(q4 , x) = q4
δ(q2 , x) = q2
δ(q2 , y) = q4
δ(q3 , x) = q4
δ(q3 , y) = q3
δ(q4 , y) = q4
2. Para cada um dos AFDs do exercı́cio anterior, indicar uma expressão regular
que represente a linguagem (conjunto de palavras aceitas) de cada autômato.
3. Utilizando a função de transição estendida δ ∗ no exercı́cio 1.c), mostrar passo
a passo a verdade ou falsidade da computação:
(a) δ ∗ (q0 , 00001) = q4
(b) δ ∗ (q3 , 0001) = q4
(c) δ ∗ (q2 , 000101) = q4
(d) δ ∗ (q1 , 001110) = q4
4. Encontrar uma expressão regular que represente a linguagem dos seguintes
autômatos mostrados na Fig. 3.15, (a) e (b)
65
3.7. EXERCı́CIOS
(a)
(b)
Figura 3.15: Autômatos Determinı́sticos
5. Seja M o autômato finito determinı́stico
M:
QP
= {q0 , q1 , q2 }
= {0, 1}
F = {q2 }
δ(q0 , 0) = q0
δ(q0 , 1) = q1
δ(q1 , 0) = q2
δ(q1 , 1) = q1
δ(q2 , 0) = q2
δ(q2 , 1) = q0
(a) Mostrar o gráfico de estados para M
(b) Mostrar em diagramas as computações de M para processar as palavras
0100, 111011, 101010 e 11100. Mencione quais são as palavras aceitas
por M
(c) Dar uma expressão regular para L(M)
6. Verificar que a palavra 00101 não é aceita pela máquina M3
7. Construa autômatos finitos determinı́sticos que aceitem cada uma das seguintes linguagens:
66
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
(a) {w ∈ {a, b}∗ | cada a em w é imediatamente precedida por um b}.
(b) {w ∈ {0, 1}∗ |w tem 0101 como uma sub-palavra}.
(c) {w ∈ {4, 5}∗ |w tem 45 e 54 como sub-palavras}.
(d) {w ∈ {a, b}∗ |w tem exatamente um sı́mbolo a }.
(e) {w ∈ {0, 1}∗ |w tem pelo menos um sı́mbolo 1 }.
(f) {w ∈ {0, 1}∗ |w tem no máximo dois sı́mbolos 0 }.
(g) {w ∈ {a, b}∗ |w = w1 aw2 com |w1 | ≥ 2, w2 ≤ 4 }.
8. Construir um AFD que aceite a linguagem:
(a) todas as palavras sobre {a, b} nas quais a sub-palavra ab ocorre pelo
menos duas vezes
(b) todas as palavras sobre {m, n} que começam com m e terminam com nn.
(c) todas as palavras sobre {0, 1, 2} nas quais cada 1 é seguido por, pelo
menos, dois sı́mbolos 2.
9. Desenhe diagramas de estado para autômatos finitos não determinı́sticos que
reconheçam essas linguagens:
(a) (ab)∗ (ba)∗ ∪ aa∗
(b) ((01 ∪ 001)∗ 0∗ )∗
(c) ((a∗ b∗ a∗ )∗ b)∗
10. Um homem deve cruzar um rio de largura grande transportando em sua canoa
um de três objetos ”perecı́veis”cada vez. Enquanto transportar um deles para
o outro lado, os outros dois devem ficar. Os objetos podem ser: onça-galinhamilho, leão-ovelha-alfafa, lobo-ovelha-alfafa, tigre-galinha-milho, lobo-cabrarepolho, etc. Simule o processo de transporte através de um autômato finito
não-determinı́stico (Q, Σ, δ, q0 , F) mostrando:
(a) O diagrama de estados da ”maquina”
(b) O conjunto de estados Q
(c) O alfabeto do autômato
(d) A função de transição
(e) Os estados inicial e finais q0 e F
11. Seja N um AFND cujo diagrama de estados esta na Fig. 3.16
67
3.7. EXERCı́CIOS
a
b
a
q0
q1
b
a
a
q2
Figura 3.16: Autômato Não-Determinı́stico N
(a) Construir a tabela de transição (função δ) de N
(b) Mostrar graficamente todas as computações da palavra aaabb em N
(c) A palavra aaabb está na linguagem L(N) ?
12. Encontrar um AFD que aceite a linguagem definida pelo autômato da Fig.
3.17
0
0
q4
q5
0
q0
q3
0
0
q1
0
q2
Figura 3.17:
13. Mostrar o diagrama de estados para o autômato que aceite:
(a) o conjunto de palavras sobre {1, 2, 3} onde a soma dos elementos é
divisı́vel por 6.
(b) o conjunto de palavras sobre {a, b} que contém um número par de ba’s
68
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
(c) o conjunto de palavras sobre {a, b} cujo tercer e último sı́mbolo é b.
14. Construir um AFND tal que:
(a) não tenha mais que cinco estados e aceite a linguagem L = {0101n |n ≥
0} ∪ {010n |n ≥ 0}
(b) não tenha mais de três estados e aceite a linguagem {ab, abc}∗
(c) tenha exatamente três estados e que aceite palavras do tipo an ou bm ak
com n ≥ 1, m, k ≥ 0
(d) tenha quatro estados e aceite palavras do tipo an ou bm a com n ≥ 0, m ≥
1
15. Para o autômato da Fig. 3.18, determinar δ ∗ (q0 , a) e δ ∗ (q1 , λ)
q0
a

q1

q2
Figura 3.18:
Capı́tulo 4
Gramáticas Livre de Contexto
Definição 4.1 Regra, produção, regra de produção
Seja V um conjunto de sı́mbolos chamados de variáveis ou sı́mbolos não-terminais
e seja Σ um conjunto chamado alfabeto ou sı́mbolos terminais. Os conjuntos V e Σ
são disjuntos. Uma regra de produção p ou simplesmente regra ou produção,
é um elemento do conjunto
{ (A, w)|A ∈ V, w ∈ (V ∪ Σ)∗ }
O elemento p =(A,w) se escreve geralmente como
A→w
e é conhecida como uma A-regra. A produção A → λ é chamada de regra nula
ou λ-regra.
A seta → pode-se ler como ”é definido por”.
Definição 4.2 Gramática
Uma gramática G é uma quádrupla ordenada G = (V, Σ, P, S) onde:
V é o conjunto finito de sı́mbolos variáveis ou não-terminais,
Σ é um conjunto finito de sı́mbolos terminais (alfabeto),
P é um conjunto de regras de produção, e
S é um elemento distinguido (especial) de V, chamado de sı́mbolo inicial (de
partida ou ”start”).
Os conjuntos V e Σ são disjuntos
Exemplo 4.1
A quádrupla G1 = (V, Σ, P, S) onde:
V = {A,B,C,D,S}
Σ = {0, 1}
P={
69
70
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
S
A
A
A
C
B
B
B
D
−→
−→
−→
−→
−→
−→
−→
−→
−→
AB
AC0
AC1
101
0
BD0
BD1
010
1
}
é uma gramática.
Exemplo 4.2
A quádrupla QuatroOper = (V, Σ, P, S) onde:
V = {K, Op, Som, Mul, Dif, Div, A, B, S}
Σ = {a, b, (, ), +, ∗, −, /}
P={
Som −→ +
S −→ Op
Mul −→ *
S −→ K
K −→ (Op)(Op)
Dif −→ Op −→ ASomB
Div −→ /
Op −→ AMulB
A −→ a
A −→ b
Op −→ ADifB
B −→ a
Op −→ ADivB
B −→ b
}
também é uma gramática.
Gramáticas são utilizadas para gerar palavras bem formadas a partir de um alfabeto. O passo fundamental no processo de geração consiste em transformar uma
palavra pela aplicação de uma regra de produção. Por exemplo, a aplicação da regra
A −→ w à variável A na palavra uAv produz a palavra uwv
Se A −→ w então uAv ⇒ uwv
O prefixo u e o sufixo v no lado esquerdo de uAv ⇒ uwv definem o contexto na
qual a variável A ocorre. Quando u e v são nulas em todas as regras de produção,
dizemos que a gramática é livre de contexto. Se u ou v não são nulas, então
dizemos que a gramática é sensı́vel ao contexto.
Definição 4.3 Gramática Livre de contexto, Context-Free Grammars, CFG
Uma gramática G = ( V, Σ, P, S) é chamada livre de contexto se todas as
produções em P tem a forma
A −→ x
onde A∈V e x ∈ (V ∪ Σ)∗
Exemplo 4.3
G = ( V, Σ, P, S) é uma gramática livre de contexto, onde:
71
V = { A, B, S}
Σ = {a, b}
P ={S −→ AB, A −→ Aa, B −→ Bb, A −→ a, B −→ b }
S é o sı́mbolo de partida.
Notação.- As produções:
α → β1 , α → β2 , . . . , α → βk ,
podem ser escritas como:
α → (β1 , β2 , . . . , βk )
ou
α → β1 |β2 | . . . |βk
Definição 4.4 Palavra derivável
Uma palavra w é derivável de v se existe uma seqüência finita de aplicações de
regras de produção de uma gramática que transformam v em w
v ⇒ w1 ⇒ w2 ⇒ ... ⇒ wn = w
∗
A derivabilidade de w a partir de v, é denotado por v ⇒ w
Exemplo 4.4 De acordo com as produções da gramática G1, temos
S ⇒ AB ⇒ AC1B ⇒ (AC0)C1B ⇒ (10100)01B ⇒ (10100)01010
∗
logo a palavra 1010001010 é derivável de S, ou S ⇒ 1010001010
Definição 4.5 Conjunto de palavras deriváveis
Seja G = (V, Σ, P, S) uma gramática livre de contexto e seja v ∈ (V ∪Σ)∗ . O
conjunto de palavras deriváveis de v é definido recursivamente como:
• Base: v é derivável de v.
• Passo Recursivo: Se u = xAy é derivável de v e A → w ∈ P, então xwy é
derivável de v.
• Fecho: Somente as palavras construı́das de v pela aplicação finita do passo
recursivo, são deriváveis de v.
Observações:
• A regra → é um elemento da relação V × (V ∪Σ)∗
• A regra ⇒ é um elemento da relação (V ∪Σ)+ × (V ∪Σ)∗
+
• O sı́mbolo ⇒ significa derivabilidade usando uma ou mais aplicações da regra.
n
• A derivação de w a partir de v de comprimento n é denotado por v ⇒ w.
• Quando mais de uma gramática é considerada, então utilizamos a notação
∗
v ⇒ w para indicar a gramática G.
G
72
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
4.1
Gramáticas e Linguagens
Definição 4.6 Forma sentencial, Linguagem de uma gramática
Seja G = {V, Σ, P, S} uma gramática livre-de-contexto. Então:
• Uma palavra w ∈ (V ∪Σ)∗ é uma forma sentencial de G se existe uma
∗
derivação S ⇒ w em G.
∗
• Uma palavra w ∈ Σ∗ é uma sentença de G se existe uma derivação S ⇒ w
em G.
∗
• A linguagem de G, denotada por L(G), é o conjunto { w ∈ Σ∗ |S ⇒ w }.
Neste caso, dizemos que G gera cada palavra em L(G).
De acordo com a definição anterior, ressaltamos que:
◦ As formas sentenciais são as palavras deriváveis do sı́mbolo inicial da gramática.
◦ As sentenças são as formas sentenciais que contém somente sı́mbolos terminais.
◦ A linguagem de uma gramática é o conjunto de sentenças geradas pela gramática
Exemplo 4.5 Considerando a gramática G1 do Exemplo 4.4 temos:
◦ A palavra w=A00C1B é uma forma sentencial de G1, pois existe uma derivação
S⇒A00C1B da forma: S ⇒ AB ⇒ AC1B ⇒ (AC0)C1B ⇒ (A00)C1B
◦ A palavra w= 1010001010 é uma sentença de G1, pois existe uma derivação
S⇒1010001010 da forma S ⇒ AB ⇒ AC1B ⇒ (AC0)C1B ⇒ (10100)01010
Definição 4.7 Linguagem livre-de-contexto, Gramáticas equivalentes
Um conjunto de palavras L sobre um alfabeto Σ é chamado de linguagem livrede-contexto se existe uma gramática livre de contexto que gera L. Duas gramáticas
são equivalentes, se elas geram a mesma linguagem.
Exemplo 4.6
Considere a gramática MiniG = (W, Σ, P, S), onde
W = { S, A, N, V, F} ∪Σ
Σ = {Pedro, grande, verde, queijo, comeu}
F → N,
F → AF,
S → FVF,
A → grande,
P={
}
A → verde,
N → queijo
N → Pedro
V → comeu
(5 sı́mbolos)
Esta é uma gramática para uma parte do idioma português: S significa sentença,
A para adjetivo, N para substantivo, V para verbo e F para frase. O conjunto de
sı́mbolos terminais Σ também pode ser escrito como Σ = {p, g, v, q, c}
73
4.1. GRAMÁTICAS E LINGUAGENS
As seguintes são algumas ”palavras” em L(G2):
Pedro comeu queijo
Pedro grande comeu queijo verde
queijo grande comeu Pedro
queijo grande comeu queijo grande verde grande verde verde
pcq
pgcqv
qgcp
A seguir, apresentamos as derivações para obter a palavra ’Pedro comeu queijo’:
S ⇒ FVF
⇒ NVF
⇒ Pedro VF
⇒ Pedro comeu F
⇒ Pedro comeu N
⇒ Pedro comeu queijo
Podemos facilmente verificar que a palavra pvcqv (Pedro verde comeu queijo
verde) não é gerada pela gramática MiniG.
P
Exemplo 4.7 Consideremos a gramática G3 = {V, , P, S} onde
V = {S, A}
Σ = {a, b}
P = { S → AA, A → AAA |bA |} Ab | a
então mostraremos algumas derivações da palavra ababaa
S ⇒ AA
⇒ aA
⇒ aAAA
⇒ abAAA
⇒ abaAA
⇒ ababAA
⇒ ababaA
⇒ ababaa
S
⇒AA
S
⇒AAAA
⇒ aAAA
⇒ abAAA
⇒ abaAA
⇒ ababAA
⇒ ababaA
⇒ ababaa
⇒AA
⇒ Aa
⇒ AAAa
⇒ AAbAa
⇒ AAbaa
⇒ AbAbaa
⇒ Ababaaa
⇒ ababaa
S ⇒ AA
⇒ aA
⇒ aAAA
⇒ aAAa
⇒ abAAa
⇒ abAbAa
⇒ ababAa
⇒ ababaa
Nas duas primeiras colunas, cada aplicação de uma regra nas derivações transforma a primeira variável que ocorre mais à esquerda da palavra. Esta propriedade
é chamada de derivação mais à esquerda. Similarmente, na terceira coluna do
exemplo, cada aplicação de uma regra transforma a variável que ocorre mais à direita
da palavra. Esta propriedade é chamada de derivação mais à direita.
Definição 4.8 Regra Diretamente Recursiva
Uma A-regra da forma A → uAv é chamada Regra Diretamente Recursiva e
pode gerar infinitas cópias de u seguidas de A e igual número de v’s. Uma variável A
é chamada de recursiva se existe uma derivação A ⇒ uAv. Uma derivação da forma
A ⇒ w ⇒ uAv, onde A não está em w, é chamada de derivação indiretamente
recursiva.
74
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
4.2
Exemplos de Gramáticas e Linguagens
Exemplo 4.8
Seja G a gramática dada pelas produções:
S → aSa | aBa
B → bB | b
Então L(G) = {an bm an |n > 0, m > 0}
Exemplo 4.9 Uma gramática é construı́da para gerar o conjunto de palı́ndromos
sobre {a, b}. Então as regras de produção são:
S→a|b|λ
S → aSa | bSb
Exemplo 4.10
As gramáticas G1 e G2 geram palavras sobre {a, b} que contém
exatamente dois b’s. A linguagem L(G1) ou L(G2) é a∗ ba∗ ba∗ .
G1: S → AbAbA
G2: S → aS | bA
A → aA | λ
A → aA | bC
C → aC | λ
G1 requer somente duas variáveis, pois as três instâncias de a∗ são geradas pela
mesma A-regra.
Exemplo 4.11 A gramática G3 gera a linguagem de todas as palavras de tamanho
par sobre {a, b}.
S → aO | bO | λ
O → aS | bS
A estratégia pode ser generalizada para construir palavras de tamanho divisı́vel
por 3, por 4, etc. As variáveis S e O servem como contadores. Um S ocorre em
uma forma sentencial quando um número par de terminais tem sido gerados. Um
O registra a presença de um número ı́mpar de terminais.
Exemplo 4.12 Forma de Backus-Naur.- Existe outra notação para gramáticas,
chamada de Forma de Backus-Naur ou BNF, que é usada para descrever as produções
de uma gramática livre de contexto para linguagens de programação. Especificamente:
• O sı́mbolo ::= é usado para substituir →
• Cada sı́mbolo não terminal é inserido dentro de < >
• Todas as regras de produção com o mesmo sı́mbolo não terminal no lado
esquerdo, são escritas em uma declaração com todos os lados direitos listados
a direita de ::=, separados por linhas verticais |. Por exemplo, as produções
A → aB, A → b, A → BC, são escritas na forma:
<A> ::= a <B> | b | <B><C>
4.3. TIPOS DE GRAMÁTICAS
75
Consideremos a linguagem de programação C e uma das suas instruções: o if simples:
if ( condição ) { conjunto-de-instruções }
Podemos escrever esta instrução utilizando uma BNF da seguinte forma:
< if > ::= if <cond-logica> { <corpo-instr> }
<cond-logica> ::= (<expr><relacao><expr>)|
<cond-logica><oper-log><cond-logica>
<expr> ::= <termo><outros-termos>
<outros-termos> ::= <oper-arit><termo><outros-termos> |λ
<oper-arit> ::= +|−
<termo> ::= <fator><mais-fatores>
<mais-fatores> ::= <oper-mul><fator><maisfatores> |λ
<oper-mul> ::= ∗| /
<fator> ::= <identif> | <intnum> |(<expressao>)
<relacao> ::= == | > | < | >= | <= | !=
<identif> ::= <letra> (<letra> | <digito>)∗
... ::= ...
Exemplo 4.13
Consideremos as seguintes regras a serem utilizadas por uma
gramática qualquer:
S → aB | bA | λ
A → aC | bS
B → aS | bC
C → aA | bB
Então a interpretação de cada variável é a seguinte:
S : número par de a’s e número par de b’s
A : número par de a’s e número par de b’s
B : número ı́mpar de a’s e número par de b’s
C : número ı́mpar de a’s e número ı́mpar de b’s.
Quando a variável S está presente, a palavra derivada satisfaz a especificação de
um número par de a’s e um número par de b’s. A aplicação de S → λ remove a
variável da forma sentencial, produzindo uma palavra na linguagem L.
4.3
Tipos de Gramáticas
Gramáticas são classificadas de acordo com as classes de regras de produção permitidas. A seguinte classificação hierárquica deve-se a Noam Chomsky (1956). Assumimos que G = { V, Σ, P, S} e α, β ∈ V.
• Tipo 1: Sem restrições nas regras de produção.
• Tipo 2: Se cada regra de produção é da forma α → β onde |α| ≤ |β|, ou da
forma α → λ.
76
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• Tipo 3: Se cada regra de produção é da forma A → β, isto é, o lado esquerdo
da regra de produção é um sı́mbolo não terminal.
• Tipo 4: Se cada regra de produção é da forma A → (a|aB), isto é, o lado
esquerdo é um sı́mbolo não terminal, e o lado direito é um único sı́mbolo
terminal ou um sı́mbolo terminal seguido de um sı́mbolo não terminal, ou da
forma S → λ
Outra classificação para gramáticas também pode ser:
• Sensı́vel ao Contexto
• Livre de Contexto
• Regulares
Definição 4.9 Gramática sensı́vel ao contexto
Uma gramática G é dita ser sensı́vel ao contexto se as regras de produção são da
forma:
α1 Aα2 → α1 βα2
O nome sensı́vel ao contexto deve-se ao fato que podemos substituir a variável A
por β somente quando A está entre α1 e α2 .
Definição 4.10 Gramática livre de contexto
Uma gramática é dita ser livre de contexto se as regras de produção são da forma:
A→β
O nome livre de contexto deve-se ao fato que podemos substituir a variável A por β
independentemente do lugar onde A aparece.
4.4
Gramáticas e Linguagens Regulares
Definição 4.11 Gramática regular
Uma gramática regular é uma gramática livre de contexto na qual cada regra de
produção tem uma das seguintes formas:
A→a
A → aB
A→λ
onde A, B são sı́mbolos não terminais e a é um sı́mbolo terminal.
Definição 4.12 Linguagem regular
Uma linguagem é regular se é gerada por uma gramática regular.
Definição 4.13 Gramática linear à direita, GLD
Uma Gramática Linear à Direita(GLD) é uma gramática livre de contexto onde
4.4. GRAMÁTICAS E LINGUAGENS REGULARES
77
cada regra de produção têm uma das seguintes formas:
A→w
A → wB
A → λ,
∗
onde w ∈ Σ
Definição 4.14 Gramática Linear à Esquerda, GLE
Uma Gramática Linear à Esquerda(GLE) é uma gramática livre de contexto
onde cada regra de produção têm uma das seguintes formas:
A→w
A →Bw
A → λ,
∗
onde w ∈ Σ
Definição 4.15 Árvore de Derivação
∗
Seja G = (V, Σ, P, S) uma gramática livre de contexto e seja S ⇒ w uma derivação.
∗
A árvore de derivação, AD, de S ⇒ w é uma árvore ordenada que pode ser
construı́da iterativamente como segue:
1. Inicializar a AD com a raiz S
2. Se A → x1 x2 ...xn com xi ∈ (V ∪Σ) é uma regra de produção na derivação
aplicada à palavra uAv, então agregar x1 , x2 , ..., xn como filhos de A na árvore.
3. Se A → λ é uma regra de produção na derivação aplicada à palavra uAv, então
agregar λ como o único filho de A na árvore
Exemplo 4.14
Seja G uma gramática com as produções:
S → aAB, A → Bba, B → bB, B → c
A palavra w = acbabc pode ser derivada de S como segue:
S ⇒ aAB → a(Bba)B ⇒ acbaB ⇒ acba(bB) ⇒ acbabc
então a árvore de derivação é mostrada na Fig. 4.1.
78
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
S
a
S
A
S →
B
a
S
A
a
A
B
b
B
aAB
B
a
b
A → Bba
S
S
A
B
a
B → c
c
a
B
B
a
b
B → bB
b
a
B
B
A
b
B
a
b
c
B→ c
B
c
Figura 4.1: Árvore de Derivação
4.5
Gramáticas Regulares e Autômatos
Uma gramática livre de contexto é chamada regular se cada regra é da forma A
→ aB | a | λ. Cada palavra derivável em uma gramática regular contém, no máximo,
uma variável (sı́mbolo não-terminal) que, se presente, ocorre como o sı́mbolo mais
à direita. A derivação termina se é aplicada uma das regras A → a ou A → λ.
Consideremos a linguagem L = a+ b+ gerado pela gramática G e aceito pelo
autômato não-determinı́stico M, como mostrado na Fig. 4.2. A palavra para teste
é aabb.
Derivação
Computação
S ⇒ aS
(S,aabb) `M (S, abb)
⇒ aaA
`M (A, bb)
⇒ aabA
`M (A, b)
⇒ aabb
`M (Z, λ)
Palavra Processada
a
aa
aab
aabb
Uma computação em um autômato começa com a palavra de entrada, seqüencialmente processa o sı́mbolo mais à esquerda, e termina quando a palavra completa
79
4.5. GRAMÁTICAS REGULARES E AUTÔMATOS
G: S → aS | aA
A → bA | b
a
S
a
b
A
b
Z
M
Figura 4.2: Gramática e Autômato
foi analisada. Uma geração começa com o sı́mbolo de inı́cio S da gramática e agrega
sı́mbolos terminais ao prefixo da forma sentencial derivada. A derivação termina com
a aplicação da λ-regra ou de uma regra onde o lado direito é um sı́mbolo terminal.
O exemplo mostra a correspondência entre a geração de uma palavra terminal
em uma gramática e o processamento de uma palavra por uma computação de um
autômato.
Teorema 4.1. Seja
G=(V, Σ, P, S)
uma gramática regular, e seja
M = (Q, Σ, δ, S, F)
um autômato finito não-determinı́stico, definido como segue:
(
V ∪ {Z}
• Q=
V
onde Z ∈ V, se P contém a regra A → a
em outro casso.
• δ(A,a) = B quando A → aB ∈ P
δ(A,a) = Z quando A → a ∈ P
(
{A|A → λ ∈ P } ∪ {Z} se Z ∈ Q
• F =
{A|A → λ ∈ P }
em outro casso.
então L(M) = L(G)
Exemplo 4.15 A linguagem a∗ (a ∪ b+ ) é gerada pela gramática G e é aceita pelo
autômato M (Fig. 4.3).
G: S → aS | bB | a
B → bB | λ
Exemplo 4.16 A linguagem da gramática regular G, é o conjunto de palavras sobre
{a, b, c} que não contém a sub-palavra abc:
S → bS | cS | aB | λ
80
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
b
M:
B
a
b
S
a
Z
Figura 4.3: Exemplo de Gramática e Autômato
B → aB | cS | bC | λ
C → aB | bS | λ
O autômato correspondente é mostrado na Fig. 4.4
b, c
M:
b
b
B
S
estado
inicial
a
C
c
a
b
Figura 4.4: Outro exemplo de Gramática e Autômato
4.6
Exercı́cios
1. Dar três exemplos de gramáticas com alfabetos diferentes
2. Escreva pelo menos cinco formas sentenciais e cinco sentenças para a gramática
QuatroOper do Exemplo 4.4
3. Considere a gramática G definida pelo alfabeto Σ = {a, b, c, d} e pelas produções:
S → abSc| A
A → cAd|cd
(a) Dar uma derivação da palavra ababccddcc.
81
4.6. EXERCı́CIOS
(b) Use a notação de conjuntos para definir L(G).
4. Provar por indução que se G = ({S}, {a, b}, P, S) com P dado por S −→ aSb,
S −→ λ, então
L(G) = {an bn |n ≥ 0}
5. Considere a gramática MiniG apresentada num exemplo anterior. Qual seria a
mudança a realizar para derivar a palavra ”Pedro verde comeu queijo verde”?
6. Para cada uma das seguintes gramáticas livre-de-contexto, usar a notação
conjunto para definir a linguagem gerada pela gramática:
(a) S → aaSB | λ
B → bB | b
(b) S → abScd | A
A → cdAba | λ
(c) S → aSb | A
A → cAd | cBd
B → aBb | ab
7. Construir uma gramática sobre {a, b, c} cuja linguagem é {an b2n cm |n, m > 0}
8. Construir uma gramática sobre {a, b} cuja linguagem é {am bi an |i = m + n}.
9. Considere a gramática G determinada pelas regras:
S → abA
S→B
S → baB
S→λ
A → bS
B → aS
A→b
Construa um autômato finito não-determinı́stico M tal que L(M) = L(G).
Trace as transições de M que conduzem para a aceitação da palavra abba e
compare com uma derivação da mesma palavra em G.
10. Construir um autômato associado à gramática
S → aA | bB
A → aS | bC
B → bS | aC | λ
C → aB | bA
11. Seja M o autômato finito não-determinı́stico mostrado na Fig. 4.5 (estado
inicial = q0 , estados finais = {q0 , q2 })
82
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
M:
a
a
a
q2
q1
q0
b
b
estado inicial = q0
estados finais = { q0,q2}
Figura 4.5: Autômato e Gramática regular
(a) Construir uma gramática regular a partir de M que gere a linguagem
L(M).
(b) Dar uma expressão regular para L(M).
12. Seja G uma gramática dada pelas regras de produção seguintes:
S → aS | bA | a
A → aS | bA | b.
(a) Construir um autômato finito não-determinı́stico MN que aceite L(G).
(b) Usando a o item anterior, construir um autômato finito determinı́stico
MD que aceite L(G).
(c) Construir uma gramática regular a partir de MN que gere L(MN)
(d) Dar uma expressão regular para L(G)
Capı́tulo 5
Autômatos de Pilha
Linguagens regulares são conjuntos de palavras geradas por gramáticas regulares
e aceita por autômatos finitos. O inverso não é verdadeiro. Isto significa que nem
toda linguagem livre de contexto pode ser reconhecida por um autômato finito, pois,
algumas linguagens livre de contexto não são regulares. Daı́ a necessidade estender
a teoria para outro tipo de máquinas que reconheça linguagens livre de contexto: o
autômato de pilha.
Uma das linguagens livre de contexto que não é aceita por qualquer autômato
finito é L1 = {ai bi |i ≥ 0}. Outra linguagem com o mesmo problema é L2 =
{wwk |w ∈ {a, b}∗ }
Em resumo, algumas razões porque é necessário estender o conceito de autômato
finito padrão:
• Autômatos finitos não podem reconhecer todas as linguagens livres de contexto
• Autômatos finitos tem memória estritamente finita
• Reconhecimento de linguagens livres de contexto requerem, algumas vezes,
armazenamento de quantidades ilimitadas de informação, por exemplo, L={
an bn /n ≥ 0}
• Precisamos armazenar e comparar uma seqüência de sı́mbolos em ordem inversa, por exemplo em L = { wwR }
5.1
Autômatos de Pilha e Linguagens
Definição 5.1 Autômato de pilha
Um autômato de pilha, denotado por AuP, é uma séxtupla
M = (Q, Σ, Γ, δ, q0 , F),
83
84
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
onde
Q é um conjunto finito de estados internos da unidade de controle
Σ é um conjunto finito de sı́mbolos chamado alfabeto de entrada
Γ é um conjunto finito chamado alfabeto de pilha
q0 ∈ Q é o estado inicial.
F ⊆ Q é o conjunto de estados finais.
δ : Q × (Σ ∪ {λ}) × (Γ ∪ {λ}) → Q ×(Γ ∪ {λ}) é a função de transição
Um autômato de pilha tem dois alfabetos: um de entrada, a partir dos quais
são construı́das as palavras de entrada, e outro, o alfabeto de pilha cujos elementos
serão armazenados na pilha1 .
A pilha é representada como uma palavra de elementos de pilha com o elemento
do topo da pilha sendo o sı́mbolo mais a esquerda da palavra. Ex. BABBA. As
seguintes são as caracterı́stica s de uma pilha:
• Os elementos do alfabeto de pilha Γ são escritos com letras maiúsculas ou com
sı́mbolos diferentes do alfabeto de entrada.
• Letras gregas representam palavras de sı́mbolos de pilha. Ex. α = AABAB.
• A notação Aα representa uma pilha α com o sı́mbolo A como o elemento topo.
• Uma pilha vazia é representada pelo sı́mbolo λ
Símbolos de entrada
a b b a b b a b b a
Unidade
de
Controle
Pi l h a
cabeça de
leitura
primeiro
elemento
B topo
A
B
B
A
Figura 5.1: Autômato de Pilha
1
Uma pilha é uma estrutura do tipo LIFO (Last Input First Output). As operações mais
conhecidas são: push (inserir elementos), pop (remover elementos) e top (para saber qual é o
elemento do top)
5.1. AUTÔMATOS DE PILHA E LINGUAGENS
85
Exemplo 5.1
Considere o autômato de pilha com
Q = {q0 , q1 , q2 , q3 }
Σ = {a, b}
Λ = {A, B}
F = {q3 }
com estado inicial q0 e com as transições
δ(q0 , a, A) = {q1 , A), (q3 , λ)}
δ(q0 , λ, A) = {(q3 , λ)}
δ(q1 , a, B) = {(q1 , BB)}
δ(q1 , b, B) = {(q2 , λ)}
δ(q2 , b, B) = {(q2 , λ)}
δ(q2 , λ, A) = {(q3 , λ)}
5.1.1
Funcionamento de un Autômato de Pilha
• A computação de um autômato de pilha começa com a máquina em estado
inicial q0 , com a palavra a ser processada na fita, e com a pilha vazia.
• O AuP consulta o atual estado, o sı́mbolo de entrada e o sı́mbolo do topo da
pilha para determinar a transição da máquina. A função de transição δ lista
todas as possı́veis transições dadas pela combinação de estado, sı́mbolo e topo
de pilha. O valor da função de transição
δ(qi , a, A) = { [qj , B], [qk , C] }
indica que duas transições são possı́veis quando o autômato esta no estado qi
lendo o sı́mbolo a e tendo um A no topo da pilha. A transição:
[qj , B] ∈ δ(qi , a, A) ou δ(qi , a, A) = [qj , B]
indica para a máquina:
- mudar o estado de qi para qj
- processar o sı́mbolo a (avançar a cabeça da fita)
- remover o sı́mbolo A do topo da pilha
- inserir o sı́mbolo B no topo da pilha.
• Um argumento λ na posição da pilha indica que o valor da componente
nem deveria ser consultada nem utilizada para a transição. A aplicabilidade
da transição é completamente determinada pelas posições que não contém o
sı́mbolo λ. Uma transição δ somente é determinada pelo estado e o sı́mbolo
de entrada. A transição não consulta nem altera a pilha
• Quando um λ ocorre como argumento na posição da pilha na função δ, a
transição é aplicável. Por exemplo, a transição δ(qi , a, λ) = [qj , B] entrará em
estado qj e agregará B no topo da pilha, porém, a máquina está em estado q0
para processar o elemento a.
86
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
• Quando a posição de entrada é λ, a transição não processa nenhum sı́mbolo
de entrada. A transição somente (i) remove e (ii) insere o sı́mbolo da pilha
sem alterar o estado ou entrada.
Uma configuração de um AuP é representada por [qi , w, α] onde qi é o estado da
máquina, w a entrada não processada, e α a pilha.
A notação:
[qi , w, α] `M [qj , v, β]
indica que a configuração [qj , v, β] pode ser obtida a partir de [qi , w, α] por uma
simples transição do autômato de pilha M
Utilizando diagramas de estado, uma transição num autômato de pilha pode ser
representado como mostra a Fig. 6.2:
qi
a A/B
qj
Figura 5.2: Transição δ(qi , a, A) = { [qj , B] }
onde A/B indica substituir, no topo da pilha, o sı́mbolo A pelo sı́mbolo B.
Exemplo 5.2
Seja M definido da seguinte forma:
Q = {qo , q1 }
Σ = {a, b}
Γ = {A}
F = {q0 , q1 }
δ(q0 , a, λ) = {[q0 , A]}
δ(q0 , b, A) = {[q1 , λ]}
δ(q1 , b, A) = {[q1 , λ]}
Observa-se que processar o sı́mbolo a significa inserir (push) o elemento A na
pilha, e processar b significa retirar (pop) o topo da pilha.
A computação gerada pela palavra de entrada aabb mostra como trabalha a
máquina M:
[q0 , aabb, λ] ` [q0 , abb, A] ` [q0 , bb, AA] ` [q1 , b, A] ` [q1 , λ, λ]
Definição 5.2 Palavra aceita
Seja M = (Q, Σ, Γ, q0 , F) um AuP. Uma palavra w ∈ Σ∗ é aceita por M se existe
uma computação
[q0 , w, λ] ` [qi , λ, λ]
87
5.1. AUTÔMATOS DE PILHA E LINGUAGENS
onde qi ∈ F. Em outras palavras, uma entrada é aceita se existe uma computação
que processe a palavra completa e termine em um estado aceitável (final) com a
pilha vazia. Este tipo de aceitação é chamada de aceitação por estado final e
pilha vazia.
Definição 5.3 Linguagem de uma máquina
A linguagem de M, denotada por L(M), é o conjunto de palavras aceitas por M.
A computação que aceita uma palavra é chamada de computação com sucesso.
Uma palavra w é aceita por estado final se existe uma computação [q0 , w, λ] `∗
[qi , λ, α], onde qi é um estado aceitável e α ∈ Γ∗ . Uma linguagem aceita por estado
final é denotada LF
Exemplo 5.3 O autômato de pilha M aceita a linguagem {wcwR |w ∈ {a, b}∗ }. A
pilha é usada para armazenar a palavra w que está sendo processada.
M:
Q = {q0 , q1 }
Σ = {a, b, c}
Γ = {A, B}
F = {q1 }
δ(q1 , b, B) = {[q1 , λ]}
δ(q0 , a, λ) = {[q0 , A]}
δ(q0 , b, λ) = {[q0 , B]}
δ(q0 , c, λ) = {[q1 , λ]}
δ(q1 , a, A) = {[q1 , λ]}
A computação para a palavra de entrada abcba é a seguinte:
[q0 , abcba, λ] ` [q0 , bcba, A] ` [q0 , cba, BA] ` [q1 , ba, BA] ` [q1 , a, A] ` [q1 , λ, λ]
Como seriam as computações para as entradas aacaa e abbcbba ?
Definição 5.4 Autômato de Pilha Determinı́stico, AuPD
Um AuP é determinı́stico se existe, no máximo, uma transição que é aplicável
para cada combinação de estado, sı́mbolo de entrada e topo de pilha.
Definição 5.5 Transições compatı́veis
Duas transições [qj , C] ∈ δ(qi , u, A) e [qk , D] ∈ δ(qi , v, B) são chamadas compatı́veis
se qualquer das seguintes condições são satisfeitas:
• u=v eA=B
• u = v e A = λ ou B = λ
• A = B e u = λ ou v = λ
• u = λ ou v = λ e A = λ ou B = λ
Exemplo 5.4 A linguagem L = {ai |i ≥ 0} ∪ {ai bi |i ≥ 0} contém palavras formadas
por unicamente a’s o por igual número de a’s e b’s. A pilha do autômato finito M
que aceita L mantém um registro do número de a’s processados até ser encontrado
um b ou a palavra de entrada tenha sido processado completamente. O gráfico 5.3
mostra a máquina M.
88
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
a λ /A
q0
estado inicial
b A/ λ
λ λ/ λ
q1
M
q2
b A/ λ
estado final
estado final
λ A/ λ
Figura 5.3: Autômato de pilha para a linguagem {ai |i ≥ 0} ∪ {ai bi |i ≥ 0}
Ao processar a no estado q0 existem duas transições que são aplicáveis. Uma
palavra da forma ai bi para i > 0 é aceita por uma computação que permanece nos
estados q0 e q1 . Se uma transição ao estado q2 segue ao processamento de um a final
em uma palavra ai , a pilha é esvaziada ea entrada é aceita. Atingir o estado q2 de
outra maneira significa ter uma computação sem sucesso, pois nenhuma computação
é executada após atingir q2 .
A λ-transição a partir de q0 permite à máquina entrar no estado q2 depois de ter
sido lido uma entrada completa. Isto introduz não-determinismo na máquina.
Exemplo 5.5 A linguagem formada por palı́ndromos pares sobre {a, b} é aceita pela
máquina M (Fig. 5.4).
A linguagem é L(M) = {wwR |w ∈ {a, b}∗ }
Uma computação permanece no estado q0 enquanto processa a palavra w e entra
no estado q1 para a leitura do primeiro sı́mbolo em wR . As palavras na linguagem
L(M) não tem marcadores intermediários que induzam à mudança de estado de q0
para q1 .
Por exemplo, para processar a palavra u = abbbba, primeiro devemos identificar
a palavra w de modo que u = wwR . Logo trataremos de criar duas máquinas M1 e
M2: na primeira será processada w e, na segunda, será processada wR . Como wR é
o reverso de w, fica claro que M1 será usada para a operação push na pilha (estado
q0 ) e M2 para a operação pop (estado q1 ). A mudança de um estado para outro (de
M1 para M2) será feita usando a λ-transição. Logo M = M1 ∪ M2.
89
5.2. VARIAÇÕES DE UM AUTÔMATO DE PILHA
b λ /B
a λ /A
q0
estado inicial
λ λ/ λ
q1
b B/ λ
a A/ λ
estado final
Figura 5.4: Autômato de pilha para a palı́ndromos pares
5.2
Variações de um Autômato de Pilha
Definição 5.6 Autômato de Pilha Atômico
Um autômato de pilha é chamado de atômico se cada transição produz somente
uma das três ações: retirar o topo da pilha (pop), inserir um elemento na pilha
(push) e processar um sı́mbolo de entrada. Transições de um AuP atômico são da
forma:
[qj , λ] ∈ δ(qi , a, λ)
[qj , λ] ∈ δ(qi , λ, A)
[qj , A] ∈ δ(qi , λ, λ)
Teorema 5.1. Seja M um autômato de pilha. Então existe um autômato de pilha
atômico N com L(N) = L(M).
Definição 5.7 Transição estendida
Uma transição estendida é uma operação sobre um AuP que insere uma palavra
completa em vez de um único elemento sobre a pilha. Por exemplo, [qj , BCD] ∈
δ(qi , u, A). Um autômato de pilha que contém transições estendidas é chamado de
Autômato de Pilha Estendido.
Teorema 5.2. Seja M um autômato de pilha estendido. Então existe um autômato
de pilha N tal que L(N)=L(M)
Exemplo 5.6
Seja L ={ai b2i |i ≥ 1}. Sejam Σ = {a, b} o alfabeto de entrada,
Γ = {A} o alfabeto de pilha, e F ={q1 }. As computações são mostradas na seguinte
tabela:
90
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
AuP
Q = {q0 , q1 , q2 }
δ(q0 , a, λ) = {[q2 , A]}
δ(q2 , λ, λ) = {[q0 , A]}
δ(q0 , b, A) = {[q1 , λ]}
δ(q1 , b, A) = {[q1 , λ]}
AuP Atômico
Q = {q0 , q1 , q2 , q3 , q4 }
δ(q0 , a, λ) = {[q3 , λ]}
δ(q3 , λ, λ) = {[q2 , A]}
δ(q2 , λ, λ) = {[q0 , A]}
δ(q0 , b, λ) = {[q4 , λ]}
δ(q4 , λ, A) = {[q1 , λ]}
δ(q1 , b, λ) = {[q4 , λ]}
AuP Estendido
Q = {q0 , q1 }
δ(q0 , a, λ) = {[q0 , AA]}
δ(q0 , b, A) = {[q1 , λ]}
δ(q1 , b, A) = {[q1 , λ]}
Como seriam as computações, nos três autômatos, da palavra aabbbb ?
5.3
Autômatos de Pilha e Linguagens Livre de
Contexto
Como exemplo, consideremos uma gramática G definido pelas seguintes regras:
S → aAB | aB
A → aAB | aB
B→b
que aceita a linguagem L = {ai bi |i > 0}. Construiremos um autômato de pilha da
seguinte forma:
• Estado inicial q0 e estado final q1
• Uma S-regra da forma S → aA1 A2 ...An gera uma transição que processa o
sı́mbolo terminal a, insere as variáveis A1 A2 ...An na pilha e entra no estado q1
• O resto das computações usam os sı́mbolos de entrada e o topo da pilha para
determinar a apropriada transição.
• A função de transição δ é definido diretamente das regras:
δ(q0 , a, λ) = {[q1 , AB], [q1 , B]}
δ(q1 , a, A) = {[q1 , AB], [q1 , B]}
δ(q1 , b, B) = {[q1 , λ]}
Teorema 5.3. Seja L uma linguagem livre de contexto. Então existe um autômato
de pilha que aceita L.
Demonstração. [SUD 05]
Teorema 5.4. A classe de linguagens aceitas por autômatos de pilha é exatamente
a classe de linguagens livres de contexto.
Demonstração. [LEW 00], pág. 134
5.3. AUTÔMATOS DE PILHA E LINGUAGENS LIVRE DE CONTEXTO
5.3.1
91
Construção de gramáticas livres de contexto a partir
de autômatos de pilha
I. As regras de uma gramática livre de contexto são construı́das a partir das
transições do autômato de pilha. A gramática é desenhada de modo que a
aplicação de uma regra corresponde a uma transição em um AuP.
II. Seja M = (Q, Σ, Γ, δ, q0 , F) uma autômato de pilha. Um autômato de pilha
estendido N com transição φ é construı́da a partir de M, incrementando δ com
as transições:
Se [qj , λ] ∈ δ(qi , u, λ) então [qj , A] ∈ φ(qi , u, A) para cada A∈ Γ.
Se [qj , B] ∈ δ(qi , u, λ) então [qj , BA] ∈ φ(qi , u, A) para cada A∈ Γ.
III. Uma gramática G = (V, Σ, P, S) é construı́da a partir das transições de N.
• O alfabeto de G é o alfabeto de entrada de N
• As variáveis de G são o sı́mbolo de inı́cio S e os objetos da forma hqi , A, qj i,
onde os q’s são os estados de N e A∈ Γ ∪ {λ}
• A variável hqi , A, qj i representa a computação que começa no estado q1 ,
termina no estado qj e remove o sı́mbolo A da pilha.
As regras de G são construı́das da seguinte forma:
i. S → hq0 , λ, qj i para cada qj ∈ F
ii. Cada transição [qj , B] ∈ δ(qi , x, A), onde A ∈ Γ ∪ {λ}, gera o conjunto de
regras:
{hqi , A, qk i → xhqj , B, qk i | qk ∈ Q}
iii. Cada transição [qj , BA] ∈ δ(qi , x, A), onde A ∈ Γ, gera o conjunto de
regras:
{hqi , A, qk i → xhqj , B, qn ihqn , A, qk i | qk , qn ∈ Q}
iv. Para cada estado qk ∈Q, temos hqk , λ, qk i → λ
Exemplo 5.7
M:
Seja M um autômato de pilha definido da seguinte forma:
Q = {q0 , q1 }
Σ = {a, b, c}
Γ={A}
F = {q1 }
δ(q0 , a, λ) = {[q0 , A]}
δ(q0 , c, λ) = {[q1 , λ]}
δ(q1 , b, A) = {[q1 , λ]}
As transições δ(q0 , a, A) = {[q0 , AA]} e δ(q0 , c, A) = {[q1 , A]} são agregadas a M
para construir N. As regras da gramática G são dadas na Tabela 5.1.
A linguagem de M é o conjunto {an cbn | n ≥ 0}
Para visualizar o relacionamento entre computações de um autômato de pilha e
derivações na gramática associada, usamos a palavra de entrada w = aacbb
92
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Transição
δ(q0 , a, λ) = {[q0 , A]}
Regra
S → hq0 , λ, q1 i
hq0 , λ, q0 i → ahq0 , A, q0 i
hq0 , λ, q1 i → ahq0 , A, q1 i
δ(q0 , a, A) = {[q0 , AA]}
hq0 , A, q0 i → ahq0 , A, q0 ihq0 , A, q0 i
hq0 , A, q1 i → ahq0 , A, q0 ihq0 , A, q1 i
hq0 , A, q0 i → ahq0 , A, q1 ihq1 , A, q0 i
hq0 , A, q1 i → ahq0 , A, q1 ihq1 , A, q1 i
δ(q0 , c, λ) = {[q1 , λ]}
hq0 , λ, q0 i → chq1 , λ, q0 i
hq0 , λ, q1 i → chq1 , λ, q1 i
δ(q0 , c, A) = {[q1 , A]}
hq0 , A, q0 i → chq1 , A, q0 i
hq0 , A, q1 i → chq1 , A, q1 i
δ(q1 , b, A) = {[q1 , λ]}
hq1 , A, q0 i → bhq1 , λ, q0 i
hq1 , A, q1 i → bhq1 , λ, q1 i
hq0 , λ, q0 i → λ
hq1 , λ, q1 i → λ
Tabela 5.1: Regras de G construı́das a partir de transições
[q0 , aacbb, λ]
` [q0 , acbb, A]
` [q0 , cbb, AA]
` [q1 , bb, AA]
` [q1 , b, A]
` [q0 , λ, λ]
S ⇒ hq0 , λ, q1 i
⇒ ahq0 , A, q1 i
⇒ aahq0 , A, q1 i
⇒ aachq1 , A, q1 i
⇒ aacbhq1 , λ, q1 i
⇒ aacbhq1 , A, q1 i
⇒ aacbbhq1 , λ, q1 i
⇒ aacbb
Teorema 5.5. Seja M um autômato de pilha. Então existe uma gramática livre de
contexto G tal que L(G) = L(M)
Lema 5.1. Se hqi , A, qj i ⇒ w onde A ∈ Γ ∪ {λ}, então existe uma computação
[qi , w, A] ` [qj , λ, λ]
Lema 5.2. Se [qi , w, A] ` [qj , λ, λ] onde A ∈ Γ ∪ {λ}, então existe uma derivação
hqi , A, qj i ⇒ w
5.4. FORMAS NORMAIS DE CHOMSKY E GREIBACH
5.4
93
Formas Normais de Chomsky e Greibach
Definição 5.8 Forma Normal de Chomsky
Uma gramática livre de contexto G = (V, Σ, P, S) está em forma normal de
Chomsky se cada regra de produção tem uma das seguintes formas:
i. A → BC
ii. A → a
iii. S → λ
onde B,C ∈ V - {S}.
Definição 5.9 Forma Normal de Greibach
Uma gramática livre de contexto G = (V, Σ, P, S) está em forma normal de
Greibach se cada regra de produção tem uma das seguintes formas:
i. A → aA1 A2 ...An
ii. A → a
iii. S → λ
onde a ∈ Σ e Ai ∈ V - {S} para i = 1, 2, ..., n.
Lema 5.3. Seja G uma gramática livre de contexto em forma normal de Chomsky e
seja A ⇒ w uma derivação de w ∈ Σ com árvore de derivação T. Se a profundidade
de T é n, então o comprimento de w é menor o igual que 2n−1
Lema 5.4. Lema do Bombeamento. Seja L uma linguagem livre de contexto.
Existe um número k, dependente de L, de modo que qualquer palavra z ∈ L com
|z| > k pode ser escrito z = uvwxy onde
i. |vwx| ≤ k
ii. |v| + |x| > 0
iii. uv i wxi y ∈ L, para i ≥ 0
Exemplo 5.8
A linguagem L = {ai bi ci |i ≥ 0} não é livre de contexto.
Considere k o número do lema de bombeamento, então w = ak bk ck = uvwxy.
Pode ser provado que não é possı́vel este tipo de decomposição.
Exemplo 5.9 A linguagem L = {ai bj ai bj |i, j ≥ 0} não é livre de contexto. Consideramos aqui z = ak bk ak bk = uvwxy
94
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Exemplo 5.10 A linguagem L ={w ∈ a∗ | |w| é primo } não é livre de contexto.
Assume-se que L é livre de contexto (contradição) e que n é primo maior que k.
Então a palavra an = uvwxy. Seja m = |u| + |w| + |y|. O comprimento de qualquer
palavra |uv i wxi y| = m + i(n − m).
Em particular, |wv n+1 wxn+1 y| = m + (n + 1)(n − m) = n(n − m + 1) não é primo,
logo a palavra não está em L. Assim, L não é livre de contexto.
5.5
Exercı́cios
1. Seja
Q
Σ
Γ
F
M um autômato de pilha definido como:
= {q0 , q1 , q2 }
δ(q0 , a, λ) = {[q0 , A]}
= {a, b}
δ(q0 , λ, λ) = {[q1 , λ]}
= {A}
δ(q0 , b, A) = {[q2 , λ]}
= {q1 , q2 }
δ(q1 , λ, A) = {[q1 , λ]}
δ(q2 , b, A) = {[q2 , λ]}
δ(q2 , λ, A) = {[q2 , λ]}
(a) Descrever a linguagem aceita pela máquina M.
(b) Mostrar o diagrama de estados para M.
(c) Mostrar todas as computações para as palavras aab, abb, aba em M.
(d) Mostrar que aabb e aaa são palavras da linguagem L(M).
2. Construir autômatos de pilha que aceitem cada uma das seguintes linguagens:
(a) {ai bj ck |i + k = j}
(b) {ai bj |i 6= j}
(c) {ai+j bi cj |i, j > 0}
(d) {a3i bi |i ≥ 0}
3. Seja G = (V, Σ, P, S) uma gramática livre de contexto. Defina um autômato
de pilha estendido M na seguinte forma:
Q = {q0 }
Σ = ΣG
Γ = ΣG ∪ V
F = {q0
δ(q0 , λ, λ) = {[q0 , S]}
δ(q0 , λ, A) = {[q0 , w] | A → w ∈ P }
δ(q0 , a, a) = {[q0 , λ] | a ∈ Σ}
Provar que L(M) = L(G)
4. Provar que cada uma das seguintes linguagens não é livre de contexto:
5.5. EXERCı́CIOS
(a) {ai b2i ai | i ≥ 0}
(b) {ai bj ck | 0 < i < j < k}
(c) {wwR w | w ∈ {a, b}∗ }
95
96
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Capı́tulo 6
Máquinas de Turing
6.1
Decidibilidade, Computabilidade e Computadores
Em 1936, com a idade de 24 anos, Alan M. Turing1 consagrou-se como um dos
maiores matemáticos do seu tempo quando fez antever aos seus colegas que era
possı́vel executar operações computacionais sobre a teoria dos números por meio
de uma máquina que tivesse embutidas as regras de um sistema formal. Embora
propriamente não existisse tal máquina, Turing enfatizou desde o inı́cio que tais
mecanismos poderiam ser construı́dos. Sua descoberta abriu uma nova perspectiva
no esforço de formalizar a matemática, e, ao mesmo tempo, marcou fortemente a
história da computação.
Em sua brilhante solução para um dos problemas chave discutidos pelos formalistas, Alan Turing descreveu em termos matematicamente precisos como um sistema
formal automático, com regras muito simples de operação, pode ser poderoso. Um
sistema formal automático é um dispositivo fı́sico que manipula automaticamente
os sı́mbolos de um sistema formal de acordo com as regras dele. A máquina teórica
de Turing era tanto um exemplo da sua teoria da computação como uma prova de
que certos tipos de máquinas computacionais poderiam, de fato, serem construı́das.
Quando ele uniu matemática e lógica na forma de uma máquina, Turing tornou
possı́veis sistemas processadores de sı́mbolos. Propôs ainda que a grande maioria dos
problemas inteligı́veis poderiam ser convertidos para a forma ”encontre um número
n tal que ...”. E, mais importante do que esta ligação entre as abstrações do nosso
1
Alan Mathison Turing nasceu em Paddington, Londres, em 1912. Morreu em Manchester
em 1954. Foi um dos grandes pioneiros do mundo da computação. Seu nome inspirou os conhecidos
termos Máquina de Turing e Teste de Turing. Como matemático aplicou o conceito de algoritmo a
computadores digitais. Trabalhou na implementação das máquinas COLOSSUS, ACE (Automatic
Computing Engine), MADAM (Manchester Automatic Digital Machine)
97
98
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
sistema cognoscitivo e a realidade concreta dos números - buscada pelos pesquisadores do campo da inteligência artificial -, foi a descoberta feita por Turing de que os
números eram elementos mais importantes como sı́mbolos, neste caso, do que como
elementos de cálculo.
O que faz o raciocı́nio humano quando executa um cálculo, perguntou Turing. Ele
definiu que os cálculos mentais consistem de operações para transformar números em
uma série de estados intermediários que progridem de um para outro de acordo com
um conjunto fixo de regras, até que uma resposta seja encontrada. Algumas vezes
usamos papel e lápis para não perdermos o estado dos nossos cálculos. As regras
da matemática exigem definições mais rı́gidas que aquelas descritas nas discussões
metafı́sicas sobre os estados da mente humana, e Turing concentrou-se na definição
destes estados de tal maneira que fossem claros e sem ambigüidades, para que tais
definições pudessem ser usadas para comandar as operações da máquina.
Turing começou com uma descrição precisa de um sistema formal, na forma
de ”tabela de instruções”que descreviam quais movimentos a fazer para qualquer
configuração possı́vel dos estados no sistema. Ele então provou que a descrição
destas informações, que os passos de um sistema axiomático formal semelhante à
lógica, e o estados da máquina que fazem os ”movimentos”em um sistema formal
automático são equivalentes entre si. Estes conceitos estão todos subjacentes na
tecnologia atual dos computadores digitais, que foram possı́veis somente uma década
depois da publicação de Turing.
Turing provou que para qualquer sistema formal existe uma máquina de Turing
que pode ser programada para imitá-lo. Era este sistema formal genérico, com a
habilidade de imitar qualquer outro sistema formal, o que Turing procurava. Tais
sistemas chamam-se Máquinas de Turing Universais. A teoria foi estabelecida pela
primeira vez em um ’paper’ que tinha o tı́tulo ”On Computable Numbers, with an
application on the Entscheidungsproblem”.
Um pequeno parêntesis para falar do ”Entscheidungsproblem”, isto é, o problema
da decidibilidade. Em 1900, no Segundo Congresso Internacional de Matemática,
realizado em Paris, David Hilbert propôs uma lista de problemas de envergadura,
cuja solução ”desafiaria futuras gerações de matemáticos”. Vários destes problemas
dessa famosa lista foram desde então resolvidos, sendo que alguns resistem até hoje
e permanecem ainda em aberto. O décimo problema da lista de Hilbert era de enunciado bastante simples: descreva um algoritmo que determina se uma dada equação
diofantina do tipo P (u1 , u2 , ..., uN ) = 0, onde P é um polinômio com coeficientes
inteiros, tem uma solução dentro do conjunto dos inteiros. Em ’computês’: escreva
um programa que tem por entrada uma equação diofantina, e que dá por saı́da um
sim ou não, conforme a equação dada tenha ou não soluções inteiras. O programa
não precisa encontrar a solução da equação, somente se tal solução existe. Se a
entrada for x2 − y 2 + xy − 11 = 0, então o programa após um número finito de
passos, deve responder sim, pois esta equação tem solução inteira (x=3, y=2 é uma
99
6.2. MÁQUINA DE TURING PADRÃO
solução). Já se a entrada fosse x2 + y 2 + xy − 11 = 0, a resposta deveria ser não,
pois esta equação não possui soluções inteiras.
A Máquina de Turing era a resposta de Alan Turing à questão metamatemática
de Hilbert. Turing estabeleceu um modelo formal de algoritmo e um pouco depois
Church proporia que qualquer procedimento efetivo poderia ser realizado por uma
Máquina de Turing (Tese de Church). Quer dizer, qualquer processo aceito por nós
homens como um algoritmo é precisamente o que uma Maquina de Turing pode
fazer. A idéia de computabilidade começa a ser delineada.
6.2
Máquina de Turing Padrão
Nem autômatos finitos nem autômatos de pilha são capazes de reconhecer linguagens
do tipo L = {an bn cn | n ≥ 0}. Para resolver este problema foram criados outro
dispositivo chamado Máquina de Turing. Isto não significa que tal dispositivo seja
uma extensão dos autômatos.
Definição 6.1 Máquina de Turing Padrão
Uma Máquina de Turing Padrão
P é uma tupla
M = (Q, , Γ, δ, q0 )
onde Q é um conjunto finito de estados, Γ um conjunto finito P
chamado alfabeto de
fita, Γ contém um sı́mbolo especial B que representa um branco,
é um subconjunto
de Γ - {B} chamado alfabeto de entrada, δ é uma função parcial:
δ : Q × Γ −→ Q × Γ × {L, R}
chamada função de transição, e q0 ∈Q o estado inicial.
A fita de uma máquina de Turing se estende infinitamente em uma direção (a
direita). As posições da fita são numeradas usando números naturais, com a primeira
posição (a mais a esquerda) numerada com 0.
0
1
2
3
4
5
a
a
b
b
b
...
q0
Figura 6.1: Fita da Máquina de Turing
...
100
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
6.2.1
Funcionamento da Máquina de Turing
A Máquina de Turing funciona da seguinte maneira:
i. A computação começa com a máquina no estado inicial q0 e a cabeça leitora
da fita examinando a posição 0 (a primeira).
P
ii. A entrada, uma palavra de ∗ , é escrita na fita começando na posição 1.
iii. A posição 0 e o resto da fita, assume-se estar em branco. O alfabeto da fita Γ
fornece todos os sı́mbolos adicionais que podem ser utilizados na computação.
iv. A transição esta formada por três ações:
• mudança de estado,
• escrever um sı́mbolo no quadrado examinado pela cabeça leitora, e
• mover a cabeça leitora
A direção do movimento é especificado pela terceira componente da transição:
uma L indica move uma posição na fita à esquerda (Left), e uma R indica
mover uma posição a direita (Right).
i
i
x
y
qi
qj
Figura 6.2: Transição δ(qi , x) = [qj , y, L]
A transição da Fig. 6.2, muda o estado qi para qj , substitui o sı́mbolo x pelo
y, e move a cabeça leitora uma posição a esquerda (L).
A habilidade da Máquina de Turing de se movimentar nas duas direções e
processar espaços em branco (B) introduz a possibilidade da computação continuar indefinidamente.
v. A Máquina de Turing pára (stop, halt) quando encontrar um par (estado,
sı́mbolo) para os quais nenhuma transição é definida. Quando uma transição
indicar que se deve movimentar para a esquerda da posição 0, entendemos este
fato como uma terminação anormal. Note-se que na definição de Máquina
de Turing não foram considerados os estados finais.
101
6.2. MÁQUINA DE TURING PADRÃO
vi. As computações da Máquina de Turing são sobre palavras do alfabeto de
entrada.
vii. Uma Máquina de Turing pode ser representada por um diagrama de estados.
A transição δ(qi , x) = [qj , y, D] | D ∈ {L, R} é representada por um arco de qi
para qj rotulada por x/yD.
viii. Uma configuração esta formada por o estado, a fita e a posição da cabeça
leitora. Uma configuração é denotada por uqi vB, onde todas as posições a
direita de B são brancos e uv é a palavra desde a posição inicial da fita até B.
Brancos (B) podem ocorrer em uv.
A notação uqi vB indica que a máquina está em estado qi examinando o
primeiro sı́mbolo de v e que todos os espaços a direita de B são brancos.
Obviamente, a sub-palavra u indica a parte já processada.
O inı́cio da computação tem a seguinte configuração: q0 BwB, onde w é a
palavra a ser processada.
ix. As representações das configurações da máquina podem ser utilizadas para
mostrar as computações da Máquina de Turing. A notação uqi vB `M xqj yB
indica que a configuração xqj yB é obtida a partir de uqi vB por uma transição
simples de M.
Exemplo 6.1 Máquina Inversora Seja a função de transição δ de uma Máquina de
Turing Padrão M com alfabeto de entrada {a, b} na seguinte tabela:
δ
q0
q1
q2
a
b
q1 , b, R
q2 , a, L
q1 , a, R
q2 , b, L
a/a λ
b/b λ
a/b R
b/a R
M:
B/B R
q0
B
q1 , B, R
q2 , B, L
q1
B/B
q2
Figura 6.3: Diagrama de estados para a Máquina de Turing M
Consideremos a palavra de entrada abab. Então as computações são as seguintes:
q0 BababB ` Bq1 ababB ` Bbq1 babB ` Bbaq1 abB
` Bbabq1 bB ` Bbabaq1 B ` Bbabq2 aB
` Bbaq2 baB ` Bbq2 abaB ` Bq2 babaB
` q2 BbabaB
102
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
Pergunta: O que faz esta máquina de Turing? Como são as computações para a
palavra de entrada aabaa ?
Exemplo 6.2 Máquina Copiadora Seja C uma Máquina de Turing definida sobre o
alfabeto {a, b}, de modo que para cada entrada da forma BwB temos uma saı́da da
forma BwBwB.
Funcionamento: A computação copia a palavra da entrada, um sı́mbolo por vez,
começando do sı́mbolo mais a esquerda. Os sı́mbolos Y e Y da fita registram a
parte da entrada que já foi processada. O primeiro sı́mbolo não marcado na palavra
especifica o caminho a seguir a partir do estado q1 . O ciclo (q1 , q2 , q3 , q4 , q1 ) substitui
um a por um X e agrega um a à palavra que esta sendo construı́da.
X/X R
a/a R
b/b R
C:
q2
q0
B/B R
a/a R
b/b R
q3
a/X R
q1
B/B L
X/a L
Y/b L
B/B R
Y/Y R
q7
b/Y R
q5
B/B R
a/a R
b/b R
B/a L
B/b L
q6
a/a R
b/b R
q4
a/a L
b/b L
B/B L
Figura 6.4: Máquina de Turing Copiadora
Processar a palavra w = aba usando a máquina C.
6.3
Máquina de Turing como Aceitantes de Linguagens
Definição 6.2
P Palavra aceita por estado final
P
Seja M = (Q, , Γ, δ, q0 , F ) uma máquina de Turing. Uma palavra u ∈ ∗ é aceita
por estado final se a computação de M com entrada u pára em um estado final qi ∈
F . Uma computação que termina anormalmente rejeita a entrada indiferentemente
do estado final da máquina. A linguagem de M, denotada por L(M), é o conjunto
de todas as palavras aceitas por M.
103
6.3. MÁQUINA DE TURING COMO ACEITANTES DE LINGUAGENS
Definição 6.3 Linguagem recursivamente enumerável
Uma linguagem aceita por uma máquina de Turing é chamada de linguagem recursivamente enumerável. A linguagem que é aceita por uma máquina de Turing
que pára para todas as palavras de entrada, é uma linguagem recursiva.
A recursividade é uma propriedade da linguagem e não da máquina de Turing.
Exemplo 6.3
A máquina de Turing M que aceita a linguagem
L = (a ∪ b)∗ aa(a ∪ b)∗
é mostrada na Fig. 6.5.
b/b R
q0
B/B R
q1
a/a R
estado
inicial
q2
a/a R
q3
estado
final
b/b R
Figura 6.5: Máquina de Turing para (a ∪ b)∗ aa(a ∪ b)∗
Como são as computações da palavra babaa? da palavra aabb?
Exemplo 6.4
Consideremos agora a linguagem L = {ai bi ci | i ≥ 0}
Y/Y R
Z/Z R
q5
q6
a/a L
b/b L
Y/Y L
Z/Z L
estado
final
Y/Y R
q0
B/B R
B/B R
q1
B/B R
a/X R
q2
b/Y R
q3
c/Z L
q4
estado
inicial
a/a R
Y/Y R
b/b R
Z/Z R
X/X R
Figura 6.6: Máquina de Turing para {ai bi ci | i ≥ 0}
A computação da máquina da Fig. 6.6 termina satisfatoriamente quando todos
104
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
os sı́mbolos de entrada tem sido transformados em sı́mbolos de fita. A transição de
q1 para q6 aceita a palavra nula.
6.4
Critérios de Aceitação alternativos
A aceitação de uma palavra em uma máquina de Turing, definida anteriormente,
esta baseada no estado da máquina quando a computação pára. A seguir definimos
outras alternativas
• Aceitação por Parada: quando uma palavra de entrada é aceita se a computação iniciada com esta palavra produz uma parada na máquina de Turing
respectiva. Computações pelas quais a máquina termina anormalmente rejeita a palavra.
P Máquinas com este critério de aceitação são definidas pela
5-tupla (Q, , Γ, δ, q0 ) sem os estados finais.
• aceitação por estado final Uma palavra w é aceita por uma máquina de
Turing M se a computação de M com entrada w entra (porém não necessariamente termina) em um estado final
Referências Bibliográficas
[AHO 08] AHO, A.V.,Lam, M.S., Sethi, R., Ullman, J.D., Compiladores Princı́piosm, técnicas e ferramentas, São Paulo: Pearson AddisonWesley, 2008.
[AND 06] ANDERSON, J.A., Automata Theory with Modern Applications,
Cambridge: Cambridge University Press, 2006.
[DIV 00]
DIVERIO, T.A., Menezes,P.F.B., Teoria da Computação Máquinas Universais e Computabilidade, Porto Alegre: Instituto
de Informática da UFRGS: Editora Sagra Luzzatto, 2000.
[GER 01] GERSTING, J.L., Fundamentos Matemáticos para a Ciência da
Computação, Quarta Edição, LTC, Rio de Janeiro, 2001.
[HOP 01] HOPCROFT, J.E., Motwani,R., Ullman, J.D. Introduction to Automata Theory, Languages, and Computation, 2nd edition, AddisonWesley, New York, 2001.
[LEW 00] LEWIS, H.R., Papadimitriou, Ch.H. Elementos de Teoria da Computação, Porto Alegre: Bookman, 2000.
[LIN 06]
LINZ, P., An Introduction to Formal Language and Automata,
Jones & Bartlett Publishers, 2006.
[LIP 97]
LIPSCHUTZ, S., Lipson, M., Discrete Mathematics, Schaum’s Outlines Series, New York: McGraw-Hill, 1997.
[MEN 00] MENEZES, P.F.B., Linguagens Formais e Autômatos, Porto Alegre: Instituto de Informática da UFRGS: Editora Sagra Luzzatto, 2000.
[PAR 02]
PARKES, A.P., Introduction to Languages, Machines, and Logic,
New York: Springer Verlag, 2002
[PAU 06]
PAUN, G., Rozenberg, G., Salomaa, A. DNA Computing: New
Computing Paradigms, New York: Springer Verlag, 2006.
105
106
Linguagens Formais e Autômatos - Prof. Ausberto S. Castro V.
[ROD 06] RODGER, S.H.,Finley, T.W. JFLAP: An Interactive Formal Languages and Automata Package, Jones & Bartlett Pub, 2006.
[SAL 03]
SALOMAA, A., Computation and Automata, Cambridge: Cambridge University Press, 2003.
[SIP 05]
SIPSER, M., Introduction to the Theory of Computation, 2 edition, Course Technology, 2005.
[SIP 11]
SIPSER, M., Introdução à Teoria da Computação, 2 edição, São
Paulo : CENAGE Learning, 2011.
[SUD 05]
SUDKAMP, T.A. Languages and Machines - An introduction to the
Theory of Computer Science, Reading: Addison-Wesley Longman, 2005.
[WEB 07] WEBBER,A.B., Formal Language: A Practical Introduction, Beedle & Associates, Inc, 2007