Aula 2 Alfabetos, Cadeias, Linguagens

Prévia do material em texto

Linguagens Formais e 
Autômatos
Alfabetos, Cadeias e 
Linguagens
Prof. Paulo
pfanio@gmail.com
Henrique
Adaptação do Material da Profª Débora Souza
Introdução
• Alfabeto, cadeias e linguagens não são conceitos
exclusivos da computação.
• Linguagem humana.
• Nas linguagens humanas inicialmente aprende-se:
1. Letras.
2. Junção de letras para formação de palavras.
3. Utilização de palavras para formação de frases.
• O conjunto de palavras e frases formam a língua.
Introdução
• O dicionário Aurélio define linguagem como:
"o uso da palavra articulada ou escrita como 
meio de expressão e comunicação entre 
pessoas" 
• Por que adaptar tal conceito para computação?
• Ambiguidade
Alfabeto
• Na visão matemática, um alfabeto tem por
definição:
• Conjunto finito de símbolos ou caracteres.
• Portanto:
• Um conjunto infinito não é um alfabeto.
• Um conjunto vazio é um alfabeto.
• Um alfabeto geralmente é representado pela letra
grega Σ (sigma).
Alfabeto
• Exemplos:
• Σ1 = {𝑎, 𝑏, 𝑐, 𝑑}
• 𝑂 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑜𝑠 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑛𝑎𝑡𝑢𝑟𝑎𝑖𝑠 ℕ
• Σ2 = {0, 1}
• Σ3 = 𝑥,+, ,∗,
• Σ4 = {𝑎, 𝑏, 𝑎𝑎, 𝑏𝑏, 𝑎𝑏,… }
Não são exemplos de alfabetos
símbolos 
Cadeia
• É o conceito matemático que seria o mais próximo
do conceito de "palavra".
• Definição:
• Uma cadeia é uma sequência finita de zero ou mais
símbolos.
• Diferente das palavras nas línguas humanas, uma
cadeia não precisa ter um significado associado.
Cadeia
• Formada por símbolos que aparecem em
sequência.
• Pode haver símbolos repetidos.
• Quando uma cadeia é criada com os símbolos de
um alfabeto Σ , dizemos que ela é uma “cadeia sobre
Σ”.
Cadeia
• Exemplos
• Alfabetos:
• Σ1 = 𝑎, 𝑏, 𝑐, 𝑑
• Σ2 = {0, 1}
• Cadeias sobre Σ1:
• ab
• da
• Cadeias sobre Σ2:
• 0001
• 11010110
Cadeia
• Existe ainda as cadeias vazias.
• Cadeias sem símbolos.
• É representada pela letra 𝜀 (épsilon).
• Portanto, se Σ representa um alfabeto então:
• Σ∗denota o conjunto de todas as palavras possíveis
sobre Σ
• Σ+ representa o conjunto de todas as palavras sobre Σ
excluindo-se a palavra vazia, ou seja, Σ+ = Σ∗- {𝜀}
Cadeia 
• Exemplos:
• Cadeias sobre Σ1:
• ε
• ab
• da
• cada
• Cadeias sobre Σ2:
• ε
• 00
• 001
• 11010110
Subcadeia
• 𝑎1 . . 𝑎𝑛 é subcadeia de 𝑏1 . . 𝑏𝑚 se a cadeia 𝑎1 . . 𝑎𝑛
é igual a algum trecho contínuo da cadeia 𝑏1 . . 𝑏𝑚.
• Exemplos:
• aba é subcadeia de aabaa
• bb não é subcadeia de aabaa
• 100 é subcadeia de 100
• ε é subcadeia de 100
Toda cadeia é subcadeia dela própria.
A cadeia vazia é subcadeia de qualquer cadeia.
Prefixo e sufixo 
• Prefixo/sufixo de uma cadeia é qualquer sequência de
símbolos inicial/final da cadeia.
• Qualquer prefixo/sufixo de uma cadeia é uma
subcadeia.
• Exemplos:
• Alfabeto: Σ1 = 𝑎, 𝑏, 𝑐, 𝑑
• Cadeia sobre Σ1: abdc
• Prefixo: ε, a, ab, abd, abdc
• Sufixo: ε, c, dc, bdc, abdc
Linguagem
• Definição:
• Uma linguagem formal ou simplesmente linguagem é
um conjunto de cadeias sobre um alfabeto.
• Cada linguagem formal é formada de cadeias de
um único alfabeto.
• Se as cadeias forem formadas com um alfabeto Σ,
dizemos que a linguagem é uma “linguagem sobre
Σ”.
Linguagem
• Linguagens podem ser finitas, infinitas ou vazias.
• Exemplo:
• Alfabeto
• Σ1 = 𝑎, 𝑏, 𝑐, 𝑑
• Σ2 = {0, 1}
• Exemplos de linguagens finitas sobre Σ2
• 𝐿1 = {00, 01, 11}
• 𝐿2 = {0, 001, 1111}
Linguagem
• Observação sobre linguagem infinita:
• Devido a impossibilidade de listar todos os elementos de uma
linguagem infinita, podemos definir este tipo de linguagem na
notação de conjuntos ou dando apenas uma descrição informal
dela.
• Exemplos de linguagem infinita sobre Σ1
• O conjunto de palíndromos (palavras que tem a mesma leitura
da esquerda para a direita e vice-versa) sobre um alfabeto.
• 𝐿3 = {𝑎, 𝑎𝑎, 𝑎𝑏𝑎, 𝑏𝑏, 𝑏𝑎𝑏, … }
• 𝐿4 é a linguagem das cadeias sobre Σ1 que começam com d.
• Exemplo de linguagem vazia sobre Σ1
• 𝐿5 = { }
Operações sobre cadeias
• Tamanho da cadeia
• O comprimento ou tamanho de uma cadeia w,
representado por |w|, é o número de símbolos que
compõem a cadeia.
• A quantidade total de símbolos de uma cadeia inclui os
símbolos que aparecem mais de uma vez.
• Exemplos:
• |a| = 1
• |aba| = 3
• |ε| = 0
Operações sobre cadeias
• Concatenação de cadeias
• Recebe duas cadeias e produz uma nova cadeia
acrescentando, ao final da primeira, todos os símbolos
da segunda cadeia.
• Esta operação pode ser representada colocando-se um
“.” entre as cadeias ou simplesmente colocando as
cadeias lado a lado sem o uso de nenhum sinal.
Operações sobre cadeias
• Concatenação de cadeias
• Exemplos:
• 01 . 10 = 0110
• a . bb = abb
• ε . 101 = 101
Qualquer concatenação envolvendo a cadeia vazia e alguma 
outra cadeia tem como resultado sempre essa outra cadeia.
Operações sobre cadeias
• Autoconcatenação
• Faz concatenações entre 𝑘 ocorrências repetidas da
cadeia, para um valor natural 𝑘 constante.
• (𝑎1 . . 𝑎𝑛)
𝑘 = 𝑎1 . . 𝑎𝑛 𝑎1 . . 𝑎𝑛 …(𝑎1 . . 𝑎𝑛)
• Exemplos:
• 1011 = 101
• 𝑎 𝑏3 = 𝑎 𝑏. 𝑏. 𝑏 = 𝑎𝑏𝑏𝑏
• (𝑏𝑎𝑎)0= 𝜀
• 𝜀2 = 𝜀. 𝜀 = 𝜀
Toda cadeia autoconcatenada zero vezes 
terá como resultado a cadeia vazia.
A cadeia vazia autoconcatenada qualquer número 
𝑘 de vezes resulta sempre nela própria.
Operações regulares (sobre 
linguagens)
• União
• O resultado da operação de união é uma linguagem que
contem todas as cadeias de L e 𝑀.
• Ex.: L ∪𝑀
• Exemplos:
• {bab, aa, bb} υ {aa, bb} = {bab, aa, bb}
• {aa, b} υ { } = {aa, b}
Operações regulares (sobre 
linguagens)
• Concatenação
• É representada por um pequeno círculo.
• 𝐿 ∘ 𝑀
• Aplica a concatenação entre cadeias várias vezes.
• O conjunto de todas as cadeias que se puder gerar será
o resultado da operação L ∘ M.
• Exemplos:
• {01, 11} ∘ {aab, b} = {01aab, 01b, 11aab, 11b}
• {101, 000} ∘ { } = { }
Operações regulares (sobre 
linguagens)
• Estrela
• Um pouco diferente das operações sobre linguagens
apresentadas anteriormente.
• Se aplica a uma única linguagem.
• Operação unária.
• Funciona justapondo qualquer número de cadeias para
obter uma nova linguagem.
• Inclui o zero como possibilidade.
• A cadeia vazia ε sempre fará parte.
• Exemplo:
• L = {00, 11}, temos que L* = {ε, 0011, 001100, 11110011, ...}.
Exercício
1) Nas questões abaixo, considere que o alfabeto é
B = {a, b, 0, 1}.
a. Mostre quatro cadeias sobre o alfabeto.
b. Crie duas linguagens finitas sobre o alfabeto.
c. Crie quatro linguagens infinitas sobre o alfabeto sendo
que duas delas devem ser descritas por descrição
informal.
Exercício
2) Nas questões abaixo, mostre o resultado de cada
operação. Considere que o alfabeto é {a, b, c}.
a. aaa . bbc
b. ε . bba
c. (ca)3
d. (aaab)1
e. ca é subcadeia de ccca?
f. cca é prefixo de ccba?
Exercício
3. Dado A={a, aa} e B={bc, cc}, compute o resultado
de cada operação.
a. A ∘ B
b. B ∪ A
c. B*