A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 2 de 49

class ∈ Σ∗, mas
class /∈ Lport e AuLa ∈ Σ
∗
, mas AuLa /∈ Lport.
DEFINIÇÃO 0.10. Uma operação importante sobre palavras é a concatena-
ção. Sejam w1, w2 ∈ Σ∗. Definimos a palavra w1.w2, ou simplesmente w1w2
como a palavra obtida escrevendo-se a palavra w1 e, imediatamente após o úl-
timo símbolo de w1, os símbolos de w2. Isto é, se w1 = α1α2 . . . αn ∈ Σ∗
(|w1| = n) e w2 = β1β2 . . . βt ∈ Σ∗ (|w2| = t), então w1w2 ∈ Σ∗ e w1w2 =
α1α2 . . . αnβ1β2 . . . βt, com |w1w2| = n+ t.
OBSERVAÇÃO. A concatenação de palavras é associativa, mas não comuta-
tiva. Além disso, para qualquer palavra w, temos que w.ε = ε.w = w.
EXEMPLO 0.11. Seja Σ = {0, 1}, w1 = 0101 e w2 = 11100. Então,
w1.w2 = 010111100 e w2.w1 = 111000101.
3. Operações sobre Linguagens
Como linguagens são conjuntos de palavras em um alfabeto, várias operações
sobre linguagens originam-se na teoria de conjuntos. Da mesma forma, o conheci-
mento dos resultados elementares da teoria de conjuntos é muito útil para o estudo
das linguagens formais.
4 0. INTRODUÇÃO
(1) União:
L1 ∪ L2 = {w : w ∈ L1 ou w ∈ L2}.
EXEMPLO 0.12. Seja Σ = {0, 1}, L1 = {00, 11, 000} e L2 =
{00, 101, 100}. Então L1 ∪ L2 = {00, 11, 000, 101, 100}.
(2) Interseção:
L1 ∩ L2 = {w : w ∈ L1 e w ∈ L2}.
EXEMPLO 0.13. Sejam Σ, L1 e L2 como no exemplo anterior. En-
tão L1 ∩ L2 = {00}.
(3) Diferença:
L1 − L2 = {w : w ∈ L1 e w /∈ L2}.
OBSERVAÇÃO. Uma outra notação para a diferença de conjuntos é
L1\L2.
EXEMPLO 0.14. Sejam Σ, L1 e L2 como nos exemplos anteriores.
Então L1 − L2 = {11, 000}.
OBSERVAÇÃO. Ao contrário das operações de união e interseção, a
operação de diferença não é comutativa. Isto é, L1 − L2 6= L2 − L1.
(4) Complemento:
L = {w : w /∈ L}.
OBSERVAÇÃO. Se L é uma linguagem sobre o alfabeto Σ, isto é, se
L ⊆ Σ∗, então L ∪ L = Σ∗ e L = Σ∗ − L.
OBSERVAÇÃO. A seguinte igualdade é sempre verdadeira: L1 −
L2 = L1 ∩ L2.
4. EXERCÍCIOS 5
(5) Concatenação:
A concatenação de linguagens é definida a partir da operação de con-
catenação de palavras.
L1.L2 = {w1.w2 : w1 ∈ L1 e w2 ∈ L2}.
EXEMPLO 0.15. Sejam Σ, L1 e L2 como nos exemplos anterio-
res. Então L1.L2 = {0000, 00101, 00100, 1100, 11101, 11100, 00000,
000101, 000100}.
OBSERVAÇÃO. Se L1 e L2 são conjuntos finitos, então |L1.L2| ≤
|L1| × |L2|.
OBSERVAÇÃO. Assim como a concatenação de palavras, a conca-
tenação de linguagens não é comutativa, isto é, L1.L2 6= L2.L1.
OBSERVAÇÃO. Temos que L.{ε} = {ε}.L = L e L.∅ = ∅.L = ∅.
(6) Estrela de Kleene:
L∗ = {ε} ∪ L ∪ L.L ∪ L.L.L ∪ . . .
OBSERVAÇÃO. Temos que ∅∗ = {ε} e {ε}∗ = {ε}.
4. Exercícios
(1) Sejam A e B conjuntos, prove que:
a) ∅ ∪A = A;
b) ∅ ∩A = ∅;
c) se A ⊂ B então A ∩B = A;
d) se A ⊂ B então A ∪B = B;
e) A ∩A = A = A ∪A;
f) A ∪B = B ∪A e A ∩B = B ∩A;
g) A ∪ (B ∪ C) = (A ∪B) ∪ C;
h) A ∩ (B ∩ C) = (A ∩B) ∩ C;
6 0. INTRODUÇÃO
i) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C);
j) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C);
k) A ∩ (A ∪B) = A;
l) A ∪ (A ∩B) = A;
m) A \ (B ∩ C) = (A \B) ∪ (A \ C);
n) A \B = A∩B onde B é o complemento de B no conjunto universo,
isto é o conjunto que contém todos os elementos com que estamos
trabalhando;
o) (A ∩B) = A ∪B;
p) (A ∪B) = A ∩B;
q) A = A;
r) A \B = A \ (B ∩A);
s) B ⊂ A se, e somente se, A ∩B = ∅;
t) (A \B) \ C = (A \ C) \ (B \ C) = A \ (B ∪ C);
u) A ∩B = ∅ e A ∩B = ∅ se e somente se A = B.
(2) Considere as afirmações abaixo: prove as verdadeiras e dê um contra-
exemplo para as falsas.
a) se A ∪B = A ∪ C então B = C;
b) se A ∩B = A ∩ C então B = C.
(3) Sejam A, B e C conjuntos, prove que:
a) A× (B ∩ C) = (A×B) ∩ (A× C);
b) A× (B ∪ C) = (A×B) ∪ (A× C);
c) A× (B \ C) = (A×B) \ (A× C);
(4) Explique a diferença entre ∅ e {ε}. Mostre que ∅.L = L.∅ = ∅ e {ε}.L =
L.{ε} = L para qualquer linguagem L.
(5) Mostre que (L∗)∗ = L∗ para qualquer linguagem L.
(6) Seja w uma palavra em um alfabeto Σ. Definimos o reflexo de w recur-
sivamente da seguinte maneira: εR = ε e se w = ax então wR = xRa
onde a ∈ Σ.
a) Determine (turing)R e (anilina)R.
4. EXERCÍCIOS 7
b) Se x e y são palavras no alfabeto Σ, determine (xy)R em função de
xR e yR.
c) Determine (xR)R.
(7) Sejam L1 e L2 linguagens no alfabeto Σ. Determine as seguintes lingua-
gens em função de LR1 e LR2 :
a) (L1 · L2)R;
b) (L1 ∪ L2)R;
c) (L1 ∩ L2)R;
d) L1R;
e) (L∗1)R.
(8) Mostre, por indução em n, que se L0, . . . , Ln são linguagens no alfabeto
Σ então
L0 · (L1 ∪ · · · ∪ Ln) = (L0 · L1) ∪ · · · ∪ (L0 · Ln).
(9) Sejam Σ1 e Σ2 dois alfabetos e seja φ : Σ1 → Σ∗2 uma aplicação. Estenda
φ a Σ∗1 de acordo com a seguinte definição recursiva:
• φ(ε) = ε;
• φ(xσ) = φ(a)φ(σ), onde a ∈ Σ∗1.
Se L é uma linguagem no alfabeto Σ1 defina
φ(L) = {φ(w) : w ∈ Σ∗1}.
Mostre que se L e L′ são linguagens no alfabeto Σ1 então:
a) φ(L ∪ L′) = φ(L) ∪ φ(L′);
b) φ(L ∩ L′) = φ(L) ∩ φ(L′);
c) φ(L · L′) = φ(L) · φ(L′);
Parte 1
Linguagens Regulares
CAPíTULO 1
Linguagens Regulares e Autômatos Finitos
Determinísticos
Neste capítulo, apresentamos o primeiro modelo formal de computação que
iremos estudar, os autômatos finitos determinísticos. Eles são o modelo de com-
putação menos poderoso dentre os que estudaremos. Apresentamos neste capítulo
também uma classe de linguagens formais associadas a estes autômatos, a classe
das linguagens regulares.
1. Autômatos Finitos Determinísticos (AFD’s)
DEFINIÇÃO 1.1. Um autômato finito determinístico (abreviado como AFD)
A é uma 5-upla A = (Σ, Q, q0, F, δ), onde:
• Σ é um alfabeto (lembrando que, pela definição do capítulo anterior, al-
fabetos são sempre finitos);
• Q é um conjunto finito de estados;
• q0 ∈ Q é o estado inicial;
• F ⊆ Q é o conjunto de estados finais e
• δ é a função de transição. Esta função tem o formato
δ : Q× Σ→ Q,
isto é, para cada par formado por um estado do conjunto Q e um símbolo
do alfabeto Σ, a função de transição fornece como resposta um estado
de Q.
EXEMPLO 1.2. Seja A o AFD definido pelos componentes (Σ, Q, q0, F, δ),
onde:
• Σ = {0, 1};
11
12 1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS DETERMINÍSTICOS
• Q = {q1, q2, q3};
• q0 = q1;
• F = {q3};
• A função δ é dada pela tabela abaixo.
δ 0 1
q1 q2 q1
q2 q1 q3
q3 q3 q1
Esta tabela representa que δ(q1, 0) = q2, δ(q1, 1) = q1, δ(q2, 0) = q1 e assim por
diante.
OBSERVAÇÃO. Um AFD também admite uma representação através de um
grafo direcionado com arestas rotuladas. Neste grafo, conseguimos representar os
5 componentes da tupla A = (Σ, Q, q0, F, δ). Os vértices do grafo representam
os elementos do conjunto Q. Estes vértices são representados por círculos sim-
ples, com o nome do respectivo elemento de Q escrito dentro do círculo, com uma
diferenciação para os elementos do conjunto F , que tem seus vértices representa-
dos por círculos duplos. O estado inicial q0 é demarcado por uma seta com um
I maiúsculo apontando para o vértice correspondente a este estado. Os símbolos
do alfabeto Σ aparecem como rótulos das arestas do grafo, que são rotuladas de
acordo com a função de transição δ. Se, para um determinado q ∈ Q e para um
determinado σ ∈ Σ, temos δ(q, σ) = q′, então colocamos no grafo uma aresta di-
recionada do vértice de q para o vértice de q′ e rotulamos esta aresta com o símbolo
σ.
EXEMPLO 1.3. O grafo que representa o AFD do exemplo anterior é mostrado
abaixo.
I // WVUTPQRSq1
0
,,
1
BB
WVUTPQRSq2
0
ll
1~~⑥⑥
⑥⑥
⑥⑥
WVUTPQRSONMLHIJKq31
``❆❆❆❆❆❆
0
\\
1. AUTÔMATOS FINITOS DETERMINÍSTICOS (AFD’S) 13
OBSERVAÇÃO. O autômato se chama determinístico porque, para cada par
de estado de Q e símbolo de Σ, a sua função de transição δ oferece exatamente
um estado como resposta. Ou seja, a resposta da função de transição é completa-
mente determinada. Ao representarmos a função de transição em forma de tabela,

Crie agora seu perfil grátis para visualizar sem restrições.