Aula 003 - Linguagens

Prévia do material em texto

LINGUAGENS FORMAIS E 
AUTÔMATOS
1º Semestre/2026
Prof. M.Sc. Thiago J D S Freitas
Aula 3 – Linguagens e gramáticas
Linguagens e gramáticas
• Definições de Alfabeto, Cadeias, Linguagens
• Gramática: dispositivo gerador de uma Linguagem
• Derivação de cadeias e árvores de derivação.
• Definições de Alfabeto
• Um alfabeto é um conjunto finito de símbolos ou 
caracteres.
UM CONJUNTO INFINITO NÃO É UM ALFABETO
O CONJUNTO VAZIO É UM ALFABETO
Exemplos:
{ a , b , c }
∅ (conjunto vazio)
 
• Definições de Alfabeto
O alfabeto de uma linguagem de programação como Pascal é o conjunto de 
todos os símbolos usados na construção de programas, incluindo:
• letras; 
• dígitos; 
• caracteres especiais como “>”, “/”, etc.; 
• espaço ou “branco”.
 
• Definições de Alfabeto
O alfabeto latino moderno é o seguinte conjunto de 26 símbolos: {A, B, 
C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z}. É comum 
representarmos o alfabeto pela letra Σ (sigma) . 
Outros exemplos de alfabeto são:
• Σ1 = { α, β, γ, δ,..., ω} 
• Σ2 = {0, 1} 
Com o primeiro você pode escrever palavras gregas e com o segundo 
você pode escrever palavras binárias (números na base 2).
• Definições de Cadeias
Uma cadeia de símbolos de um dado alfabeto (também chamada de 
string, palavra ou sentença) é uma sequência finita de símbolos deste 
alfabeto
Ex:
Para o alfabeto Σ1 = { α, β, γ ,δ ,...,ω} podemos escrever a cadeia "ψω ".
Para o alfabeto Σ2 = { 0,1} podemos escrever a cadeia "10001".
• Cadeias Vazias
A cadeia formada por uma sequência com nenhum símbolo é conhecida 
como a cadeia vazia. Representamos a cadeia vazia com o símbolo ε 
(Épsilon)
• Prefixo, sufixo, subpalavra
Um prefixo (respectivamente, sufixo) de uma palavra é qualquer sequência 
inicial (respectivamente, final) de símbolos da palavra.
Uma subpalavra de uma palavra é qualquer sequência de símbolos contíguos da 
palavra
• Ex:
abcb é uma palavra sobre o alfabeto { a, b, c } 
• Relativamente à palavra abcb, vale que:
• ε, a, ab, abc, abcb são todos os prefixos;
• ε, b, cb, bcb, abcb são todos os sufixos; 
• Qualquer prefixo ou sufixo de uma palavra é uma subpalavra;
• Para a palavra aa, o conjunto de todos os prefixos, de todos os sufixos e de 
todas as subpalavras é o mesmo: { ε, a, aa } 
• Comprimento de Cadeias
 Qualquer cadeia de símbolos tem um comprimento. Por exemplo,
a cadeia "10001" tem comprimento 5. A cadeia vazia é normalmente
representada em linguagens de programação como "".
• Concatenação de Cadeias
 Dadas duas cadeias, definimos sua concatenação como a 
justaposição de seus valores.
 
Por exemplo, se ω1 ="101" e ω2 ="000", sua
concatenação é "101000". 
Representamos a concatenação ω1ω2 . 
• Concatenação de Cadeias
 Considere 3 cadeias ω1, ω2 e ω3. Se formamos a concatenação de 
ω1 com ω2 e depois concatenarmos ω3 teremos a justaposição das 3 
palavras como resultado dessas operações representamos ω1ω2ω3.
Exemplos:
• Associativa: 
• (ω1ω2) ω3 = ω1(ω2ω3)
• v(w t) = (v w)t
• Elemento Neutro = ε ω = ω = ω ε
Exemplos:
Suponha o alfabeto Σ = { a, b }. Então, para as palavras v = baaaa e w = 
bb, vale que:
• v w = baaaabb 
• v ε = v = baaaa 
• Concatenação sucessiva de Cadeias
A concatenação sucessiva de uma palavra (com ela mesma) ou 
simplesmente concatenação sucessiva representada na forma de um 
expoente (suponha w uma palavra): 
 𝒘𝒏 onde n é o número de concatenações sucessivas
• é definida indutivamente a partir da operação de concatenação 
binária, como segue:
• 𝒘𝟎 = ε 
• 𝒘𝒏 = w 𝒘𝒏−𝟏, para n > 0 
Exemplos:
Sejam w uma palavra e a um símbolo. Então:
𝒘𝟑 = w w w 
𝒘𝟏 = w 
𝒂𝟓 = aaaaa 
𝒂𝒏 = aaa...a (o símbolo a repetido n vezes) 
Próxima Aula 23/02/2026
• Breve apresentação da Hierarquia de Chomsky
• Definição de Linguagens Regulares; 
• Gramática Regular: dispositivo gerador de uma 
Linguagem Regular;
• Expressões Regulares; 
 
Referências Bibliográficas 
• MENEZES, Paulo Blauth. - Linguagens formais e autômatos. 6.ed. 
V.3 - Porto Alegre, Sagra Luzzatto, 2011. 
https://integrada.minhabiblioteca.com.br/reader/books/978857
7807994/pageid/ 0 
 
https://integrada.minhabiblioteca.com.br/reader/books/9788577807994/pageid/%200
https://integrada.minhabiblioteca.com.br/reader/books/9788577807994/pageid/%200
https://integrada.minhabiblioteca.com.br/reader/books/9788577807994/pageid/%200
https://integrada.minhabiblioteca.com.br/reader/books/9788577807994/pageid/%200
https://integrada.minhabiblioteca.com.br/reader/books/9788577807994/pageid/%200
	Slide 1: LINGUAGENS FORMAIS E AUTÔMATOS
	Slide 2: Linguagens e gramáticas
	Slide 3: Definições de Alfabeto
	Slide 4: Definições de Alfabeto
	Slide 5: Definições de Alfabeto
	Slide 6: Definições de Cadeias
	Slide 7: Prefixo, sufixo, subpalavra
	Slide 8: Comprimento de Cadeias
	Slide 9: Concatenação de Cadeias
	Slide 10: Concatenação sucessiva de Cadeias
	Slide 11: Próxima Aula 23/02/2026
	Slide 12: Referências Bibliográficas