Linguagens formais e Autômatos - Capítulo 1 - P.

Blauth Menezes 1

Linguagens Formais e
Autômatos
1 Introdução e Conceitos Básicos

2 Linguagens Regulares

3 Linguagens Livre do Contexto

4 Linguagens Enumeráveis
Recursivamente e Sensíveis ao
Contexto

5 Hierarquia de Classes de
Linguiagens e Conclusões
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 2

1 Introdução e Conceitos Básicos

1.1 Introdução
1.2 Conjuntos, Relações e Funções
1.3 Lógica
1.4 Técnicas de Demonstração
1.5 Alfabetos, Palavras, Linguagens e
Gramáticas
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 3

1 Introdução e
Conceitos Básicos

1.1 Introdução
♦ Teoria das Linguagens Formais
• originariamente desenvolvida na década de 1950
• objetivo inicial
∗ desenvolver teorias relacionadas com as
linguagens naturais
• hoje
∗ importante para o estudo de linguagens
artificiais
∗ em especial, para as linguagens originárias na
Ciência da Computação
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 4

♦ Enfoques
• análise de linguagens de programação
∗ léxica
∗ sintática
• modelos de sistemas biológicos
• desenho de hardware
• relacionamentos com linguagens naturais

♦ Recentemente
• linguagens não-lineares
∗ como planares
∗ espaciais
∗ n-dimensionais.
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 5

Sintaxe e Semântica

♦ Linguagens Formais
• problemas sintáticos das linguagens

♦ Historicamente
• o problema sintático foi reconhecido antes do
problema semântico
• foi o primeiro a receber um tratamento adequado
• são de tratamento mais simples que os semânticos

♦ Conseqüência
• grande ênfase à sintaxe
• ao ponto de levar à idéia de que
∗ questões das linguagens de programação
resumiam-se às questões da sintaxe
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 6

♦ Atualmente
• teoria da sintaxe possui construções matemáticas
bem definidas e universalmente reconhecidas
como
• exemplo: Gramáticas de Chomsky.

♦ Linguagem de Programação (ou qq

modelo matemático) pode ser vista
• livremente sem qualquer significado associado
• juntamente com uma interpretação do seu
significado

♦ Sintaxe
• trata das propriedades livres da linguagem
∗ "forma"
∗ exemplo: verificação gramatical de programas

♦ Semântica
• fornece uma interpretação para a linguagem
• exemplo: um significado ou valor para um
determinado programa
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 7

♦ Conseqüentemente
• sintaxe basicamente manipula símbolos
∗ não considera os correspondentes significados
• mas, para resolver qq problema real
∗ é necessário dar uma interpretação semântica
aos símbolos
∗ exemplo: "estes símbolos representam os
inteiros"

♦ Sintaticamente "errado"
• não existe uma noção de programa "errado"
• neste caso, simplesmente não é um programa

♦ Sintaticamente "Correto"
• pode não ser o programa que o programador
esperava escrever

♦ Programa "Correto" ou "Errado"

• deve considerar se modela adequadamente o
comportamento desejado
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 8

♦ Limites entre Sintaxe e Semântica

• nem sempre são claros
• exemplo
∗ ocorrência de um nome em um programa
∗ pode ser tratado como um problema sintático
ou semântico

• entretanto, para a maioria dos problemas

relevantes
∗ a distinção entre sintaxe e semântica em
linguagens artificiais é, em geral, óbvia.
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 9

Abordagem

♦ Abordagem
• tratamento sintático de linguagens
∗ lineares
∗ abstratas

• com fácil associação às linguagens típicas da

Ciência da Computação

♦ Tipos do Formalismos usados

• Operacional
• Axiomático
• Denotacional
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 10

Operacional

♦ Autômato ou máquina abstrata

• estados
• instruções primitivas
• como cada instrução modifica cada estado

♦ Máquina abstrata
• suficientemente simples
∗ não deve permitir dúvidas sobre seu
funcionamento

• também é dito um Formalismo Reconhecedor

∗ análise de uma entrada para verificar se é
reconhecida pela máquina

♦ Principais máquinas
• Autômato Finito
• Autômato com Pilha
• Máquina e Turing
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 11

Axiomático

♦ Associam-se regras às componentes da

linguagem

♦ Regras
• permitem afirmar o que será verdadeiro
• após a ocorrência de cada cláusula
• considerando o que era verdadeiro antes da
ocorrência

♦ Formalismos axiomáticos
• Gramáticas Regulares
• Gramáticas Livre do Contexto
• Gramáticas Sensíveis ao Contexto
• Gramáticas Irrestritas

♦ Gramática também é dita um

Formalismo Gerador
∗ permite verificar se um determinado elemento
da linguagem é gerado
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 12

Denotacional

♦ Ou Formalismo Funcional

♦ Domínio (sintático)
• que permite a caracterização do conjunto de
palavras admissíveis na linguagem

• tratam-se de funções, as quais são, em geral,

composicionais (horizontalmente)
∗ o valor denotado por uma construção é
especificado em termos dos valores denotados
por suas subcomponentes

♦ Formalismo Denotacional
• Expressões Regulares
∗ é simples inferir (gerar) aos elementos da
linguagem
∗ assim, freqüentemente também é denominado
(de forma não muito precisa) como um
Formalismo Gerador
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 13

Estruturação e breve Introdução

Capítulo 1

♦ Demais tópicos deste capítulo

• introduzem conceitos básicos necessários

♦ Conjuntos, Relações, Funções e Técnicas

de Demonstração
• revisão e normalização de notações
• supõem um conhecimento prévio
• não esgotam o assunto
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 14

Capítulo 2 - Linguagens Regulares

♦ Origem dos Formalismos Autômato

Finito e Expressões Regulares
• estudos biológicos de redes de neurônios
• circuitos de chaveamentos

♦ Mais recentemente
• analisadores léxicos
∗ parte de um compilador
∗ identifica e codifica as unidades básicas de uma
linguagens como variáveis, números, etc
∗ caso particular e simples de análise sintática
• editores de textos
• sistemas de pesquisa e atualização em arquivos
∗ em geral, do tipo busca e substituição de
informações não complexas
• linguagens de comunicação homem-máquina
∗ como interface do sistema operacional
• linguagens de comunicação máquina-máquina
∗ como protocolos de comunicação
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 15

Capítulo 3 - Ling. Livre do Contexto

♦ Formalismos
• Gramáticas Livre do Contexto
• Autômato com Pilha

♦ Ênfase do estudo
• analisadores sintáticos

• historicamente
∗ desenvolvimento de analisadores sintáticos era
um problema complexo, de difícil depuração e
com eficiência relativamente baixa

• hoje, considerando o conhecimento já adquirido

relativo às Linguagens Livre do Contexto
∗ desenvolvimento de um analisador sintático é
simples (assim como a sua depuração)
∗ somente uma pequena percentagem do tempo
de processamento de um compilador é gasto
em tal atividade
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 16

Capítulo 4 Linguagens Enumeráveis

Recursivamente e Sensíveis ao Contexto

♦ Formalismos
• Máquina de Turing
∗ e eventuais variações/restrições

• Gramáticas Irrestritas e Sensíveis ao Contexto

♦ Exploram
• limites da capacidade de desenvolvimento de
reconhecedores ou geradores de linguagens

• ou seja
∗ estuda a solucionabilidade do problema da
existência de algum reconhecedor ou gerador
para determinada linguagem.
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 17

Capítulo 5 - Hierarquia de Classes de

Linguagens e Conclusões

♦ Hierarquia de Chomsky
• classifica as diversas classes de linguagens em uma
ordem hierárquica
• inclusão própria entre as classes

Linguagens Enumeráveis Recursivamente ou Tipo 0

Linguagens Sensíveis ao Contexto ou Tipo 1

Linguagens Livres do Contexto ou Tipo 2

Linguagens Regulares ou
Tipo 3

♦ Apresenta
• conclusões gerais
• perspectivas futuras
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 18

1.2 Conjuntos, Relações e

Funções
♦ Pré-requisitos
• conceitos básicos relativos à Teoria dos
Conjuntos.

Conjuntos

♦ Conjunto e Elemento
• Conjunto é uma coleção de zero ou mais objetos
distintos, denominados Elementos do conjunto.
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 19

♦ Notações
• a ∈ A, a ∉ A
• A ⊆ B ou B ⊇ A
∗ A está contido em B
∗ A é subconjunto de B
∗ B contém A

• A ⊂ B ou B ⊃ A
∗ A está contido propriamente em B
∗ A é subconjunto próprio de B
∗ B contém propriamente A

• A=B
∗ A⊆BeB⊆A
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 20

♦ Conjuntos
• número de elementos
∗ finito
∗ infinito

• conjunto finito
∗ pode ser denotado por extensão
∗ por exemplo, {a, b, c}

• conjunto vazio
∗ sem elementos (ou seja, com zero elementos)
∗ { } ou ∅

• conjunto (finito ou infinito) denotado por

compreensão

{ a  a ∈ A e p(a) } ou
{ a ∈ A  p(a) } ou
{ a  p(a) }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 21

♦ Exemplo
• a ∈ {b, a} e c ∉ {b, a};

• {a, b} = {b, a}, {a, b} ⊆ {b, a} e {a, b} ⊂ {a, b, c};

• Os seguintes conjuntos são infinitos

∗ N conjuntos dos números naturais
∗ Z conjuntos dos números inteiros
∗ Q conjuntos dos números racionais
∗ I conjuntos dos números irracionais
∗ R conjuntos dos números reais

• {1, 2, 3} = { x ∈ N  x > 0 e x < 4 }

• N = { x ∈ Z x ≥ 0 };

• conjunto dos números pares

{ y  y = 2x e x ∈ N }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 22

Operações sobre Conjuntos

♦ União
• A ∪ B = { x  x ∈ A ou x ∈ B }

♦ Intersecção
• A ∩ B = {xx ∈ A e x ∈ B}

♦ Diferença
• A - B = {xx ∈ A e x ∉ B}

♦ Complemento
• definida em relação a um conjunto fixo U
denominado universo
• A' = { x  x ∈ U e x ∉ A }

♦ Conjunto das Partes

• 2A = { S  S ⊆ A }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 23

♦ Produto Cartesiano
• A × B = { (a, b)  a ∈ A e b ∈ B }
• notação usual de A × A: A2

♦ Par ordenado
• elemento de um produto cartesiano
• denotado na forma (a, b)
• não deve ser confundido com o conjunto {a, b}
∗ a ordem é importante
∗ as duas componentes são distinguidas
∗ conceito é generalizado para n-upla ordenada,
ou seja, com n > 0 componentes

♦ Exemplo
• universo N, A = {0, 1, 2} e B = {2, 3}
∗ A ∪ B = {0, 1, 2, 3}
∗ A ∩ B = {2}
∗ A - B = {0, 1}
∗ A' = { x ∈ N  x > 2 }
∗ 2B = { ∅, {2}, {3}, {2, 3} }
∗ A × B = { (0, 2), (0, 3), (1, 2), (1, 3), (2, 2), (2, 3) }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 24

Algumas Propriedades

♦ Suponha universo U e conjuntos A, B e C

• idempotência da união e intersecção
∗ A∪A=A
∗ A∩A=A

• associatividade da união e intersecção

∗ A ∪ (B ∪ C) = (A ∪ B) ∪ C
∗ A ∩ (B ∩ C) = (A ∩ B) ∩ C

• comutatividade da união e intersecção

∗ A∪B=B∪A
∗ A∩B=B∩A

• distributividade da união e intersecção

∗ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
∗ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 25

• relativamente ao complemento
∗ (A')' = A
∗ A ∪ A' = U
∗ A ∩ A' = ∅

• leis de Morgan
∗ (A ∪ B)' = A' ∩ B'
∗ (A ∩ B)' = A' ∪ B'
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 26

Relações

♦ Relação
• subconjunto de um produto cartesiano
• R ⊆ A×B

♦ Notações
• A é denominado domínio
• B é denominado contra-domínio ou codomínio
• a R b denota (a, b) ∈ R
• relação em A: R ⊆ A × A
∗ domínio e o contra-domínio coincidem
∗ normalmente denotada por (A, R)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 27

Propriedades das Relações

♦ Sejam
• A um conjunto e R uma relação em A

♦ Reflexiva
• se, para todo a ∈ A, a R a

♦ Simétrica
• se a R b, então b R a

♦ Antissimétrica
• se a R b e b R a, então a = b

♦ Transitiva
• se a R b e b R c, então a R c

♦ Importante
• uma relação pode não ser simétrica nem
antissimétrica: não são noções complementares
• uma relação pode ser simultaneamente simétrica e
antissimétrica
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 28

♦ Exemplo
• conjunto não vazio A

• (N, ≤) e (2A, ⊆)
∗ reflexivas
∗ antissimétricas
∗ transitivas

• (Z, <) e (2A, ⊂)

∗ transitivas

• (Q, =)
∗ reflexiva
∗ simétrica
∗ antissimétrica
∗ transitiva
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 29

Relação de Ordem (R em A)

♦ Relação de Ordem
• se é transitiva

♦ Relação de Ordem Parcial

• se é reflexiva, antissimétrica e transitiva

♦ Relação de Ordem Total

• se é uma relação de ordem parcial e
• para todo a, b ∈ A, ou a R b ou b R a

♦ Exemplo: considere um conjunto não

vazio A
• relação de ordem
∗ (N, ≤), (2A, ⊆), (Z, <), (2A, ⊂) e (Q, =)

• relação de ordem parcial

∗ (N, ≤), (2A, ⊆) e (Q, =)
• relação de ordem total
∗ (N, ≤)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 30

Relação de Equivalência (R em A)

♦ Relação de Equivalência
• se for reflexiva, simétrica e transitiva

♦ Importante resultado
• cada relação de equivalência induz um
particionamento em classes de equivalência
∗ particionamento do conjunto
∗ em subconjuntos disjuntos e não vazios

♦ Exemplo
• R = { (a, b) ∈ N2  a MOD 2 = b MOD 2 }
• MOD: resto da divisão inteira
• R induz um particionamento de N
∗ subconjuntos dos pares (resto zero)
∗ subconjuntos dos ímpares (resto um)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 31

♦ Freqüentemente
• desejável estender uma relação de forma a
satisfazer determinado conjunto de propriedades

♦ Fecho de uma Relação

• R uma relação e P um conjunto de propriedades
• Fecho de R em relação ao P
∗ denotado por FECHO-P(R)
∗ menor relação que contém R e que satisfaz às
propriedades em P

♦ Dois fechos importantes

• Transitivo
• Transitivo e Reflexivo
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 32

♦ Fecho Transitivo
• P = {transitiva}
• denotado por R+ = FECHO-P(R)
• definido como segue
∗ se (a, b) ∈ R, então (a, b) ∈ R +
∗ se (a, b) ∈ R+ e (b, c) ∈ R+, então (a, c) ∈ R +
∗ os únicos elementos de R+ são os construídos
como acima

♦ Fecho Transitivo e Reflexivo

• P = {transitiva, reflexiva}

• denotado por R*, é tal que:

∗ R* = R+ ∪ { (a, a)  a ∈ A }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 33

♦ Exemplo: Grafo (direto)

• pode ser definido como uma
∗ relação (binária) A (de arestas)
∗ em um conjunto V (de vértices)

• A = {(1, 2), (2, 3), (3, 4), (1, 5)}

∗ é um grafo em V = {1, 2, 3, 4, 5}

• A* = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (3,
3), (3, 4), (4, 4), (5, 5)}

1 1

2 5 2 5

3 3

4 4
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 34

Funções

♦ Função Parcial
• relação f ⊆ A × B tal que
∗ se (a, b) ∈ f e (a, c) ∈ f, então b = c
∗ cada elemento do domínio está relacionado
com, no máximo, um elemento do contra-
domínio

• notação f: A → B

• f(a) = b denota (a, b) ∈ f

∗ f está definida para a
∗ b é imagem de a

• { b ∈ B  existe a ∈ A tal que f(a) = b }

∗ conjunto imagem de f
∗ denotado por f(A) ou Img(f)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 35

♦ Função (Total) ou Aplicação

• função parcial f: A → B onde
∗ para todo a ∈ A existe b ∈ B tal que f(a) = b

• ou seja:
∗ função parcial
∗ definida para todos os elementos do domínio

♦ Exemplo
• Adição nos naturais
∗ ad: N × N → N tq ad(a, b) = a + b
∗ função (total)

• Divisão nos inteiros

∗ div: Z × Z → Z tq div(a, b) = a/b
∗ função parcial
∗ não é definida para (a, 0) ∈ Z× Z
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 36

♦ Composição de Funções
• Sejam f: A → B e g: B → C funções
• g • f: A → C tal que
∗ (g • f)(a) = g(f(a))
∗ aplicação da função f ao elemento a e, na
seqüência, da função g à imagem f(a)

♦ Exemplo
• ad: N × N → N
• quadrado: N → N tq quadrado(a) = a2
• quadrado • ad: N2 → N
∗ (quadrado • ad)(3, 1) =
∗ quadrado(ad(3, 1)) =
∗ quadrado(4) =
∗ 16
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 37

Tipos de Funções

♦ Uma função f: A → B é

♦ Injetora
• se, para todo b ∈ B, existe no máximo um a ∈ A tal
que f(a) = b
• se cada elemento do contra-domínio é imagem de,
no máximo, um elemento do domínio

♦ Sobrejetora
• se, para todo b ∈ B, existe pelo menos um a ∈ A tal
que f(a) = b
• se todo elemento do contra-domínio é imagem de
pelo menos um elemento do domínio
♦ Bijetora
• se é injetora e sobrejetora
• se todo elemento do contra-domínio é imagem de
exatamente um elemento do domínio
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 38

♦ Exemplo
• inclusão: N → Z tq inclusão(a) = a é injetora
• módulo: Z → N tq módulo(a) = a é sobrejetora
• f: Z → N tq
∗ f(a) = 2a se a ≥ 0
∗ f(a) = 2a-1 se a < 0
∗ é bijetora
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 39

Cardinalidade de Conjuntos

♦ Cardinalidade
• de um conjunto
• é uma medida de seu tamanho
• definida usando funções bijetoras
• de um conjunto A, é representada por #A

♦ Cardinalidade Finita
• se existe uma bijeção de A com
∗ {1, 2, 3, ..., n}, n ∈ N
∗ #A = n
• ou seja
∗ é possível representar por extensão

♦ Cardinalidade Infinita
• se existe uma bijeção entre A com
∗ um subconjunto próprio de A
• ou seja
∗ retirando elementos de A
∗ pode-se estabelecer uma bijeção com A
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 40

♦ Exemplo
• f: Z → N tal que
∗ f(a) = 2a se a ≥ 0
∗ f(a) = 2a-1 se a < 0
∗ é bijetora
• N é subconjunto próprio de Z
• então Z é infinito

♦ Importante
• nem todos os conjuntos infinitos possuem a
mesma cardinalidade
• cardinal do conjunto dos números naturais N
∗ denotado por ℵ0
∗ ℵ ("alef") é a primeira letra do alfabeto
hebráico
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 41

♦ Conjunto Contável ou Contavelmente

Infinito
• se existe uma bijeção
∗ com um subconjunto infinito de N
∗ denominada Enumeração de A

• um conjunto é contável
∗ pode-se enumerar seus elementos
∗ como uma seqüência na forma a0, a1, a2, ...
• cardinal de qualquer conjunto contável
∗ ℵ0

♦ Conjunto (Infinito) Não-Contável

• caso contrário

♦ Exemplo
• Z e Q são contáveis
• IeR
∗ são não-contáveis
∗ cardinal é 2ℵ0
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 42

1.3 Lógica
♦ Lógica Booleana
• o estudo dos princípios e métodos usados para
distinguir sentenças verdadeiras de falsas

♦ Proposição
• sentença declarativa
• possui valor lógico
∗ verdadeiro
∗ falso
• usualmente denotados por V e F

♦ Proposição Sobre U
• considere um conjunto universo U
• proposição cujo valor lógico depende de x ∈ U
• usualmente denotada por p(x)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 43

♦ p sobre U
• induz uma partição de U em duas classes de
equivalências
∗ {xp(x) é verdadeira}: conjunto verdade de p
∗ {xp(x) é falsa}: conjunto falsidade de p

♦ Tautologia
• se p(x) é V para qq x ∈ U

♦ Contradição
• se p(x) é F para qq x ∈ U

♦ Exemplo
• 3 + 4 > 5 é uma proposição
• para a proposição n! < 10 sobre N
∗ {0, 1, 2, 3} é o conjunto verdade
∗ {n ∈ Nn > 3} é o conjunto falsidade

• n + 1 > n sobre N é uma tautologia

• "2n é ímpar" sobre N é uma contradição
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 44

♦ Operador
• função da forma op: An → A

♦ Operador Lógico ou Conetivo

• operador sobre o conjunto das proposições P

♦ Proposição Atômica ou Átomo

• proposição que não contém conetivos

♦ Tabela Verdade
• descreve os valores lógicos de uma proposição
• em termos das possíveis combinações dos valores
lógicos das proposições componentes
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 45

♦ Operadores Lógicos
• Operador ¬ Negação
• Operador ∧ E
• Operador ∨ Ou
• Operador → Se-Então
• Operador ↔ Se-Somente-Se

p q ¬p p∧q p∨q p→q p↔q

V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 46

♦ Operadores → e ↔ induzem
• Relação de Implicação
• Relação de Equivalência

♦ Relação de Implicação
• ⇒
• {(p, q) ∈ P2  p → q é uma tautologia}

♦ Relação de Equivalência
• ⇔
• {(p, q) ∈ P2  p ↔ q é uma tautologia}

♦ ⇒e⇔
• ⇒ é relação de ordem
• ⇔ é relação de equivalência
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 47

♦ Exemplo
• p⇒p∨q
• p∧q⇒p

p q p ∨ q p → (p ∨ q) p ∧ q (p ∧ q) → p
V V V V V V
V F V V F V
F V V V F V
F F F V F V

♦ Exemplo
• p → q ⇔ ¬q → ¬p

¬p ¬q p→q ¬q → ¬p p→q↔
¬q → ¬p
F F V V V
F V F F V
V F V V V
V V V V V
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 48

♦ Exemplo
• p → q ⇔ (p ∧ ¬q) → F

p q ¬q p→q p ∧ ¬q p→q↔
(p ∧ ¬q) → F
V V F V F V
V F V F V V
F V F V F V
F F V V F V
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 49

1.4 Técnicas de
Demonstração
♦ Teorema
• proposição p → q
∗ prova-se ser uma tautologia
∗ ou seja, p ⇒ q
• p: hipótese
• q: tese

♦ Corolário
• teorema que é uma conseqüência quase direta de
um outro já demonstrado
• ou seja, cuja prova é trivial ou imediata

♦ Lema
• teorema auxiliar que possui um resultado
importante para a prova de um outro
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 50

♦ Hipótese e Tese
• antes de iniciar uma demonstração deve-se
identificar claramente
∗ hipótese
∗ tese

♦ Exemplo
• hipótese e tese?

∩ distribui-se sobre a ∪, ou seja,

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• reescrita identificando a hipótese e a tese

se A, B e C são conjuntos quaisquer,

então A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 51

♦ Teorema na forma p ↔ q
• p ↔ q ⇔ (p → q) ∧ (q → p)
• demonstra-se
∗ "ida" (→)
∗ "volta" (←)

♦ Exemplo
A é contável sse
existe uma função bijetora entre A e o
conjunto dos números pares
• "ida" e "volta"

se um conjunto A é contável,
então existe uma função bijetora entre A e o
conjunto dos números pares
e
se existe uma função bijetora entre A e o
conjunto dos números pares,
então A é contável
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 52

♦ Algumas técnicas para demonstrar um

teorema p → q
• direta
• contraposição
• redução ao absurdo
• indução
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 53

Prova Direta

♦ Técnica
• supor a hipótese é V
• a partir da hipótese provar que a tese é V

♦ Exemplo
• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• lembre-se que
∗ X = Y sse X ⊆ Y e Y ⊆ X
∗ X ⊆ Y sse todos os elementos de X também são
elementos de Y

• é fácil verificar que

∗ p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)

• Para provar que A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

∗ A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C)
∗ (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 54

♦ Prova Direta
• Caso 1: A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
∗ Suponha que x ∈ A ∩ (B ∪ C)
x ∈ A ∩ (B ∪ C) ⇒
x ∈ A ∧ x ∈ (B ∪ C) ⇒
x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇒
(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇒
x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) ⇒
x ∈ (A ∩ B) ∪ (A ∩ C)
∗ Portanto, A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C)

• Caso 2: (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C)
∗ Suponha que x ∈ (A ∩ B) ∪ (A ∩ C)
x ∈ (A ∩ B) ∪ (A ∩ C) ⇒
(x ∈ (A ∩ B)) ∨ (x ∈ A ∩ C) ⇒
(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇒
x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇒
x ∈ A ∧ x ∈ (B ∪ C) ⇒
x ∈ A ∩ (B ∪ C)
∗ Portanto, (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).

• Logo, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 55

Prova por Contraposição

♦ Técnica
p → q ⇔ ¬q → ¬p

♦ Exemplo
n! > n + 1 → n > 2
• pode-se, equivalentemente, demonstrar por
contraposição que

n ≤ 2 → n! ≤ n + 1
• prova de que n ≤ 2 → n! ≤ n ?
∗ é suficiente testar para n = 0, n = 1 e n = 2
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 56

Prova por Redução ao Absurdo

♦ Técnica
p → q ⇔ (p ∧ ¬q) → F
• supor a hipótese p
• supor a negação da tese ¬q
• concluir uma contradição
∗ em geral, q ∧ ¬q

♦ Prova por Contra-Exemplo

• em uma demonstração por absurdo
∗ construção da contradição q ∧ ¬q
∗ apresentação de um contra-exemplo

♦ Exemplo
0 é o único elemento neutro da adição em N
• reescrevendo na forma de p → q

se 0 é elemento neutro da adição em N,

então 0 é o único elemento neutro da adição
em N
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 57

♦ Prova por Absurdo

• suponha que 0 é o neutro da adição em N
• suponha que não é o único
• seja e um neutro da adição em N tq e ≠ 0
• como 0 é neutro
∗ para qualquer n ∈ N tem-se que n = 0 + n
∗ em particular, para n = e, tem-se que e = 0 + e

• como e é elemento
∗ para qualquer n ∈ N, tem-se que n = n + e
∗ em particular, para n = 0, tem-se que 0 = 0 + e

• portanto
∗ como e = 0 + e e 0 = 0 + e, tem-se que e = 0
∗ contradição!!! pois foi suposto que e ≠ 0

• Logo, é absurdo supor que o elemento neutro da

adição em N não é único
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 58

Prova por Indução

♦ Importante
• é usada com freqüência
• é usada em proposições que dependem de N

♦ Princípio da Indução Matemática

• seja p(n) uma proposição sobre N
• p(0) é V
• se, para qualquer k ∈ N, p(k) → p(k + 1) então, para
qualquer n ∈ N, p(n) é V

♦ Nomenclatura
• p(0): base de indução.
• p(k): hipótese de indução
• p(k) → p(k + 1): passo de indução
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 59

♦ Técnica
• demonstrar a base de indução p(0)
• fixado um k, supor V a hipótese de indução p(k)
• demonstrar o passo de indução
• na realidade
∗ o princípio da indução matemática pode ser
aplicado a qualquer proposição que dependa de
um conjunto para o qual exista uma bijeção
com os naturais

♦ Exemplo
para qualquer n ∈ N tq n ≥ 0, tem-se que
1 + 2 + ... + n = (n2 + n)/2
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 60

♦ Prova por Indução

• Base de Indução
Seja n = 0. Então:
(02 + 0)/2 = (0 + 0)/2 = 0/2 = 0

Portanto, 1 + 2 + ... + n = (n2 + n)/2 é V para n = 0

• Hipótese de Indução
Suponha que, para algum n fixo tq n ≥ 0
1 + 2 + ... + n = (n2 + n)/2

• Passo de Indução.
Prova para 1 + 2 + ... + n + (n + 1)
1 + 2 + ... + n + (n + 1) =
(1 + 2 + ... + n) + (n + 1) =
(n2 + n)/2 + (n + 1) =
(n2 + n)/2 + (2n + 2)/2 =
(n2 + n + 2n + 2)/2 =
((n2 + 2n + 1) + (n + 1))/2 =
((n + 1)2 + (n + 1))/2

Portanto, 1 + 2 + ... + (n + 1) = ((n + 1)2 + (n + 1))/2

• Logo, para qq n ∈ N tq n ≥ 0, tem-se que

1 + 2 + ... + n = (n2 + n)/2
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 61

♦ Princípio da Indução Matemática ×

Definições
• o princípio da indução matemática pode ser usado
para definições
• é dita indutivamente definida
• ou recursivamente definida
• exemplo
∗ definição de Fecho
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 62

1.5 Alfabetos, Palavras,

Linguagens e Gramáticas
♦ Definição: Símbolo, Caractere
• entidades abstratas básica
• não definida formalmente

♦ Exemplo: Símbolo
∗ letras
∗ dígitos

♦ Definição: Alfabeto
• conjunto finito de símbolos

♦ Exemplo: Alfabeto
• ∑1 = {a, b, c}
• ∑2 = {0, 1, ..., 9}
• ∑3 = { }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 63

♦ Definição: Palavra, Cadeia de Caracteres,

Sentença
• sobre um alfabeto
• seqüência finita de símbolos justapostos

♦ Exemplo: Palavra
• a, abcb são palavras sobre {a, b, c}
• ε
∗ palavra vazia - sem símbolos
∗ é palavra sobre qualquer alfabeto

♦ Definição: Tamanho, Comprimento de

uma palavra
• número de símbolos que compõem a palavra
• representação
∗ w
∗ w denota uma palavra

♦ Exemplo: Tamanho de uma palavra

• abcb = 4
• ε = 0
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 64

♦ Conjuntos de Palavras sobre ∑

• ∑∗
∗ conjunto de todas as palavras sobre ∑
• ∑+
∗ ∑+ = ∑∗ - { ε }
• exemplo: para ∑ = {a, b}
∗ ∑+ = {a, b, aa, ab, ba, bb, aaa,...}
∗ ∑* = {ε, a, b, aa, ab, ba, bb, aaa,...}

♦ Definição: Prefixo, Sufixo, Subpalavra

• prefixo (sufixo)
∗ qq seqüência de símbolos inicial (final) de uma
palavra
• subpalavra
∗ qq seqüência de símbolos contígüa de uma
palavra

♦ Exemplo: para a palavra abcb

• prefixos: ε, a, ab, abc, abcb
• sufixos: ε, b, cb, bcb, abcb
• prefixos e sufixos são subpalavras
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 65

♦ Definição: Linguagem Formal

• um conjunto de palavras sobre um alfabeto

♦ Exemplo: Ling. Formal sobre ∑ = {a, b}

• conjunto vazio
• conjunto formado pela palavra vazia
∗ note-se que { } ≠ { ε }

• conjunto das palíndromos

∗ palavras que têm a mesma leitura da esquerda
para a direita e vice-versa
∗ linguagem infinita
∗ ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,... são
palíndromos
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 66

♦ Definição: Concatenação
• operação binária, definida sobre uma linguagem
• palavra formada pela justaposição das palavras
• notação
∗ justaposição dos símbolos que representam as
palavras componentes

• satisfaz às seguintes propriedades:

∗ associatividade: v(wt) = (vw)t
∗ elemento neutro (esq/dir): εw = w = wε

♦ Exemplo: Concatenação
• para v = ab e w = cd
∗ vw = abcd
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 67

♦ Definição: Concatenação Sucessiva

• concatenação sucessiva de uma palavra com ela
mesma
• indefinida para ε0

♦ Exemplo: Concatenação Sucessiva

• w3 = www
• w1 = w
• a5 = aaaaa
• an = aaa...a (a repetido n vezes)
• w0 = ε para w ≠ ε
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 68

♦ Definição: Gramática
G = (V, T, P, S):
• V
∗ conjunto finito de símbolos
∗ variáveis ou não-terminais
• T
∗ conjunto finito de símbolos
∗ terminais
∗ disjunto de V
• P
∗ conjunto finito de pares (α, β)
∗ regra de produção
∗ α é palavra de (V ∪ T)+
∗ β é palavra de (V ∪ T)*
• S
∗ elemento de V
∗ variável inicial

♦ Notação de (α, β)
• α→β
• notação abreviada para α → β1, ..., α → βn
∗ α → β1...βn
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 69

♦ Definição: Derivação
• G = (V, T, P, S) uma gramática
• Derivação é um par da relação denotada por ⇒
∗ com domínio em (V ∪ T)+
∗ contra-domínio em (V ∪ T)*
∗ representação de forma infixada

α⇒β
• ⇒ é indutivamente definida
• para qq produção S → β
∗ S é o símbolo inicial

S⇒β
• para qq par α ⇒ β
∗ onde β = βuβvβw
∗ se βv → βt é regra de P então

β ⇒ β u β tβ w

♦ Portanto, derivação
• substituição de uma subpalavra de acordo com
uma regra de produção
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 70

♦ Sucessivos Passos de Derivações

• ⇒*
∗ fecho transitivo e reflexivo da relação ⇒
∗ zero ou mais passos de derivações sucessivos

• ⇒+
∗ fecho transitivo da relação ⇒
∗ um ou mais passos de derivações sucessivos

• ⇒i
∗ exatos i passos de derivações sucessivos
∗ i é número natural
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 71

♦ Gramática é um formalismo
• Axiomático
• de Geração
∗ permite derivar ("gerar") todas as palavras da
linguagem que representa

♦ Definição: Linguagem Gerada

• G = (V, T, P, S) uma gramática
• Linguagem Gerada por G'

L(G) ou GERA(G)
• todas as palavras de símbolos terminais deriváveis
a partir do símbolo inicial S

L(G) = {w ∈ T*  S ⇒+ w}
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 72

♦ Exemplo: números naturais

• G = (V, T, P, S)
∗ V = {S, D}
∗ T = {0, 1, 2,..., 9}
∗ P = {S → D, S → DS, D → 01...9}

• uma derivação do número 243 (existe outra?)

S ⇒ DS ⇒ 2S ⇒ 2DS ⇒ 24S ⇒ 24D ⇒ 243

• portanto
S ⇒* 243
S ⇒+ 243
S ⇒6 243

• logo GERA(G)
∗ o conjunto dos números naturais
∗ sintaticamente (por quê?)
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 73

♦ Definição: Equivalência de Gramáticas

• G1 e G2 são equivalentes sse

GERA(G1) = GERA(G2)

♦ Convenções:
• A, B, C,..., S, T símbolos variáveis
• a, b, c,..., s, t símbolos terminais
• u, v, w, x, y, z palavras de símbolos terminais
• α, ß,... palavras de símbolos variáveis
e/ou terminais
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 74

♦ Exemplo: identificadores em Pascal

• G = (V, T, P, S)
∗ V = {S, C, L, D}
∗ T = {a, b, ..., z, 0, 1, 2,..., 9}
∗ P={ S → LC  L,
C → LC  DC  L  D,
L → a  b ... z,
D → 0  1 ... 9 }

♦ Exemplo: texto com aspas balanceadas

• G = (V, T, P, S)
∗ V = {E}
∗ T = {x, "}
∗ P={ S → xS  ε,
S → "S" }
 Linguagens formais e Autômatos - Capítulo 1 - P. Blauth Menezes 75

♦ Exemplo: ww
{ www é palavra de {a, b}* }
• G = ({S, X, Y, A, B, F}, {a, b}, P, S)
∗ P={ S → XY,
X → XaA  XbB, F
Aa → aA, Ab → bA, AY → Ya,
Ba → aB, Bb → bB, BY → Yb,
Fa → aF, Fb → bF, FY → ε }

• baba

S⇒
XY ⇒
XaA Y ⇒
XaYa ⇒
XbBaYa ⇒
XbaBYa ⇒
XbaYba ⇒
FbaYba ⇒
bFaYba ⇒
baFYba ⇒
baεba = baba