av1- LFAC

Elementos da matemática discreta

Conceitos

conjunto: coleção de símbolos em que o mesmo não ocorre mais de uma vez e a ordem não importa

a cardinalidade de um conjunto é uma medida do número de elementos do conjunto

símbolo: representação gráfica única e indivisível composta, por vezes, por mais de um caractere

alfabeto: conjunto de símbolos

pertencimento:∈ (pertence) e ∈/ (não pertence)

Conjunto vazio: não contém nenhum elemento, denotado por ∅ ou {}; {} = ∅ → |∅| = 0

⊆
subconjuntos: A B sse todo elemento de A for também elemento de B. Formalmente A ⊆ B ↔ ∀x
(x ∈ A→x ∈ B)

∅⊆AeA⊆A
⊆ = “é subconjunto”
Conjunto potência (powerset): denotado por 2A , onde A é um conjunto formado por todos os
possíveis subconjuntos de A

📌 exemplos
- X = {2, 3}; ∅
2X = { , {2}, {3}, {2,3}}
∅
-2^{} = { }

Produto cartesiano: é um conjunto formado por todos os pares ordenados, A × B = {(a, b) | a ∈A∧
b∈ B}, em que há relação de ordem entre os elementos, se a ≠ b, então (a, b) ≠ (b, a)

Pode-se usar notação de expoente quando A × A = A2

av1- LFAC 1
 📌 exemplos
A = {a, b, c}, B = {0, 1}, C = {#}
- A x B = {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}
- C x B = {(#, 0), (#, 1)}
- 2AxC = 2^{{(a, #), (b, #), (c, #)}}
∅
= { , {(a, #)}, {(b, #)}, {(c, #)}, {(a, #), (b, #)}, {(a, #), (c, #)}, {(b, #), (c, #)}, {(a, #), (b,
#), (c, #)}}

relação: é definida como um subconjunto de A × B, ∴ R ⊆ A × B, O conjunto de todas as relações

definíveis sobre A × B é dado por 2AxB

Uma relação sobre o conjunto A2 é uma endorrelação/autorrelação

A é o domínio e B o contradomínio

pode ser binária (pares ordenados) ou n-ária (ênuplas ordenadas)

função: relação que associa o domínio ao contradomínio em que cada elemento do domínio associa-
se a no máximo um elemento do contradomínio

Toda função é uma relação, mas nem toda relação é uma função

injetora: elementos de A com relação única a elementos de B

sobrejetora: todos os elementos de B estão ligados ao domínio A

bijetora: todos os elementos de A tem relação única com todos os elementos de B

Igualdade de cardinalidade: dois conjuntos A e B, finitos ou infinitos, possuem a mesma

cardinalidade, se existir uma função bijetora entre eles

Conceitos básicos de linguagens

Símbolo: é uma representação gráfica, indivisível, empregado na construção de cadeias.

Alfabeto: é um conjunto finito de símbolos. Não pode conter o conjunto vazio

Comprimento: quantidade de símbolos que formam uma “palavra”, desde que esteja em um alfabeto

Cadeia: é uma sequência finita de símbolos do alfabeto justapostos.

Cadeia vazia: cadeia formada por uma quantidade nula de símbolos

⚠ observação:

cadeia vazia → ε (comprimento zero)

conjunto vazio → ∅ (linguagem sem cadeias)

conjunto com somente a cadeia vazia → {ε} (linguagem com única cadeia)

conjunto com somente o conjunto vazio → { ∅}

∅ ∅
|ε| = | | = 0 // |{ε}| = |{ }| = 1

Sentença: é uma cadeia que pertence a linguagem.

Concatenação: união de cadeias

av1- LFAC 2
 é associativa e não comutativa

concatenar com cadeia vazia não faz diferença

Reverso: α = β R em que α = 123abc e β = cba321

Fechamento reflexivo e transitivo: ∑*

Fechamento transitivo: ∑+

Linguagem: é um conjunto, finito ou infinito, de cadeias de comprimento finito formadas pela

concatenação de elementos de um alfabeto finito e não-vazio.

Gramática: é um formalismo matemático utilizado para gerar sentenças que pertencem a uma
linguagem formal, consequentemente, definindo a própria linguagem.

📌 G = (V, ∑, P, S)
V = vocabulário (term. e não term.); ∑ = alfabeto (terminais)

Para uma gramática ser bem formada:

todos os símbolos terminais precisam estar no vocabulário (o vocabulário deve conter todos os
símbolos da gramática)

o vocabulário não pode ser um conjunto vazio

ser possível obter uma sentença com dito vocabulário, alfabeto, conjunto de produções e raiz

Reconhecedor: é um formalismo matemático utilizado na aceitação de sentenças que pertencem a

uma linguagem e na rejeição de todo e qualquer cadeia que não faz parte dessa linguagem.

Linguagens regulares

Linguagens geradas por gramáticas regulares recebem o nome de linguagens regulares

Uma linguagem é dita regular se pode ser reconhecida por um autômato finito determinístico (DFA)
ou por um autômato finito não-determinístico (NFA).

gramática linear à esquerda: símbolo não terminal na produção fica à esquerda (quando presente);
gramática linear à direita: símbolo não terminal na produção fica à direita (quando presente) →
ambos geram a mesma classe de linguagens

Passo-a-passo: de linear à direita (GLUD) para linear à esquerda (GLUE):

1. criar uma gramática linear à direita (S → aS; X → abS) e determinar sua linguagem → L(G1)

2. determinar o reverso da linguagem → LR (G1)

3. elaborar uma gramática que gere essa linguagem reversa (achar o padrão, inventar as
produções e escrever a gramática) → ou seja, L(G’) =LR (G1)

4. transformar G’ em G2, invertendo as regras, literalmente escrevendo as regras de produção ao

contrário, com os símbolos não terminais à esquerda

é permitida a produção de cadeia vazia

Conjuntos e expressões regulares: uma notação alternativa

linguagens definidas recursivamente sobre um alfabeto Σ

av1- LFAC 3
 ✍ conjuntos regulares:

1. L = {a, b, c}: a linguagem que contém as cadeias "a", "b" e "c".

2. L = {a^n | n ≥ 0}: a linguagem que contém todas as cadeias de "a" possíveis, incluindo
a cadeia vazia.

3. L = {a^n b^n | n ≥ 0}: a linguagem que contém todas as cadeias de "a" seguidas de "b",
onde o número de "a" é igual ao número de "b".

4. L = {0, 1}*: a linguagem que contém todas as cadeias de "0" e "1" possíveis, incluindo
a cadeia vazia.

5. L = {w | w é uma cadeia de dígitos com no máximo 3 dígitos}: a linguagem que contém

todas as cadeias de dígitos com no máximo 3 dígitos possíveis, como "1", "23" e "999".

expressões regulares: Elimina o uso dos símbolos “{” e “}”, e substitui “ ∪” por “|” ou “+”

✍ expressões regulares:

1. L1 = {0, 1, 00, 11, 000, 111, ...}:

Expressão regular: (0+1)(0+1)*

2. L2 = {w | w começa com 0 e termina com 1}:

Expressão regular: 0(0+1)*1

3. L3 = {w | w contém pelo menos um 0 e pelo menos um 1}:

Expressão regular: (0+1)*0(0+1)1(0+1)

4. L4 = {w | w contém exatamente dois 0's}:

Expressão regular: (0+1)*0(0+1)0(0+1)

5. L5 = {w | w tem comprimento par}:

Expressão regular: (0+1)(0+1)*((0+1)(0+1))

av1- LFAC 4
 ✍ comparações:

A expressão regular (ab | c∗) = (ab | (c∗)) = ((ab) | (c∗)) representa o conjunto {ε, ab,
c, cc, ccc, ...}

a(b | c)∗ representa o conjunto {a, ab, ac, abc, abb, acc, ...}

(ab | c)∗ representa o conjunto {ε, ab, c, abc, cab, abab, cc, ...}

L = {0m1n | m ≥ 0, n ≥ 0} pode ser reescrita como ((0)∗(1)∗) ou 0∗1∗.

Para m ≥ 0 e n ≥ 1, a expressão correspondente seria 0∗11∗ = 0∗1+

Σ = {a, b, c, d} e os dois subconjuntos A = {a}, B = {b, c}

Sentenças que possuem no mínimo um símbolo a:

Σ∗AΣ∗ ou (a | b | c | d)∗a(a | b | c | d)∗

Sentenças que possuem exatamente dois símbolos a:

(Σ - A)∗A(Σ - A)∗A(Σ - A)∗ ou (b | c | d)∗a(b | c | d)∗a(b | c | d)∗

Sentenças que possuem um número par de símbolos a:

((Σ - A)∗A(Σ - A)∗A(Σ - A)∗)* ou ((b | c | d)∗a(b | c | d)∗a(b | c | d)∗)*

Sentenças que iniciam com o símbolo a e terminam com o símbolo b ou c:

AΣ∗B ou a(a | b | c | d)∗(b | c)

Sentenças contendo apenas os símbolos a, b, c, com no mínimo um símbolo:

(A ∪ B)+ ou (a | b | c)+

Leis algébricas das expressões regulares

Autômatos

av1- LFAC 5
 Configuração inicial de um autômato: Configuração final de um autômato:

Estado: inicial para cada reconhecedor Estado: algum dos estados finais

Conteúdo da fita de entrada: cadeia Conteúdo da fita de entrada: alterado ou

completa a ser analisada não em relação ao inicial

Posição do cursor: apontando para o Posição do cursor: apontando para a

símbolo mais à esquerda da cadeia direita do último símbolo da cadeia

Conteúdo da memória auxiliar: inicial, Conteúdo da memória auxiliar: final e

predefinido e único predefinido

Impasse: quando não há possibilidades de movimentação a partir da configuração corrente

Autômato determinístico: havendo impasse, a cadeia é rejeitada

Autômato não-determinístico: havendo impasse, indica apenas que a particular sequência de

movimentações (thread) não reconheceu a cadeia

Aceitação: Se pelo menos uma thread atingir uma configuração final

Rejeição: Se todas as threads conduzirem a configurações não-finais

Autômatos finitos determinísticos (AFD) = (Q, Σ, δ, q0, F)

Q: conjunto de estados

Σ: alfabeto

δ: transições - um estado lendo um símbolo (Q x Σ)

q0: estado inicial (só tem um)

F: estados finais

autômatos mínimos:

| w | mod n = ∅ ; em que n = qtde de estados

| w | = n; estados = n + 2

| w | ≤ n; estados = n + 2

| w | ≥ n; estados = n + 1

av1- LFAC 6