Operações de Linguagens Formais

Prévia do material em texto

Teoria da Computação
Linguagens Formais: Operações
Vilar da Camara Neto
1o período de 2015
cbnd
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 1 / 34
Formalização de linguagens: Operações básicas
Certas operações permitem representar uma linguagem de maneira
bem mais conveniente:
I Repetição
I Fecho de Kleene e Fecho Positivo de Kleene
I Agrupamento
I Concatenação
I União
I Interseção
I Subtração
I Complemento
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 2 / 34
Repetição
O operador de repetição aparece como um “expoente” após um
símbolo e indica o número de repetições desse símbolo:
I 02 é uma sequência de dois “0”s: 00
I 15 é uma sequência de cinco “1”s: 11111
I z3 é uma sequência de três “z”s: zzz
I k0 é uma sequência de zero “k”s: λ
Na verdade, qualquer símbolo repetido zero vezes gera λ.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 3 / 34
Repetição
O operador de repetição aparece como um “expoente” após um
símbolo e indica o número de repetições desse símbolo:
I 02 é uma sequência de dois “0”s: 00
I 15 é uma sequência de cinco “1”s: 11111
I z3 é uma sequência de três “z”s: zzz
I k0 é uma sequência de zero “k”s: λ
Na verdade, qualquer símbolo repetido zero vezes gera λ.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 3 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição é muito útil na definição de linguagens:
L = {ak | k < 5}
“Conjunto de sequências de as dado que tenham menos de 5 letras.”
Ou: “Conjunto de sequências de as com menos de 5 letras.”
L = {λ, a, aa, aaa, aaaa}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 4 / 34
Repetição
O operador de repetição também pode ser aplicado sobre conjuntos
→ Neste caso, gera-se conjuntos de palavras:
I L = {0, 1}2 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 2: L = {00, 01, 10, 11}
I L = {a, b}3 é o conjunto de todas as palavras sobre {a, b} que
possuem tamanho = 3:
L = {aaa, aab, aba, abb, baa, bab, bba, bbb}
I L = {0, 1}0 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 0: L = {λ}
“Todas as palavras de tamanho = 0”: Independentemente do
alfabeto, só existe uma palavra de tamanho = 0! → λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 5 / 34
Repetição
O operador de repetição também pode ser aplicado sobre conjuntos
→ Neste caso, gera-se conjuntos de palavras:
I L = {0, 1}2 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 2: L = {00, 01, 10, 11}
I L = {a, b}3 é o conjunto de todas as palavras sobre {a, b} que
possuem tamanho = 3:
L = {aaa, aab, aba, abb, baa, bab, bba, bbb}
I L = {0, 1}0 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 0: L = {λ}
“Todas as palavras de tamanho = 0”: Independentemente do
alfabeto, só existe uma palavra de tamanho = 0! → λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 5 / 34
Repetição
O operador de repetição também pode ser aplicado sobre conjuntos
→ Neste caso, gera-se conjuntos de palavras:
I L = {0, 1}2 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 2: L = {00, 01, 10, 11}
I L = {a, b}3 é o conjunto de todas as palavras sobre {a, b} que
possuem tamanho = 3:
L = {aaa, aab, aba, abb, baa, bab, bba, bbb}
I L = {0, 1}0 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 0: L = {λ}
“Todas as palavras de tamanho = 0”: Independentemente do
alfabeto, só existe uma palavra de tamanho = 0! → λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 5 / 34
Repetição
O operador de repetição também pode ser aplicado sobre conjuntos
→ Neste caso, gera-se conjuntos de palavras:
I L = {0, 1}2 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 2: L = {00, 01, 10, 11}
I L = {a, b}3 é o conjunto de todas as palavras sobre {a, b} que
possuem tamanho = 3:
L = {aaa, aab, aba, abb, baa, bab, bba, bbb}
I L = {0, 1}0 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 0: L = {λ}
“Todas as palavras de tamanho = 0”: Independentemente do
alfabeto, só existe uma palavra de tamanho = 0! → λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 5 / 34
Repetição
O operador de repetição também pode ser aplicado sobre conjuntos
→ Neste caso, gera-se conjuntos de palavras:
I L = {0, 1}2 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 2: L = {00, 01, 10, 11}
I L = {a, b}3 é o conjunto de todas as palavras sobre {a, b} que
possuem tamanho = 3:
L = {aaa, aab, aba, abb, baa, bab, bba, bbb}
I L = {0, 1}0 é o conjunto de todas as palavras sobre {0, 1} que
possuem tamanho = 0: L = {λ}
“Todas as palavras de tamanho = 0”: Independentemente do
alfabeto, só existe uma palavra de tamanho = 0! → λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 5 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n |n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 1:
L =
{
p ∈ {0, 1}n | n ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número
de repetições de {0, 1} é no máximo 2.”
Ou: “Conjunto de palavras sobre {0, 1} com no máximo dois
dígitos.”
L = {λ, 0, 1, 00, 01, 10, 11}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 6 / 34
Repetição
Exemplo 2:
L =
{
p ∈ {0, 1}n | n > 0}
“Conjunto de palavras sobre {0, 1} com pelo menos um dígito.”
Pode ser lido como: “Conjunto de números binários”!
Note que esta linguagem possui infinitas palavras: |L| = ∞.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 7 / 34
Repetição
Exemplo 2:
L =
{
p ∈ {0, 1}n | n > 0}
“Conjunto de palavras sobre {0, 1} com pelo menos um dígito.”
Pode ser lido como: “Conjunto de números binários”!
Note que esta linguagem possui infinitas palavras: |L| = ∞.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 7 / 34
Fecho de Kleene
As repetições “zero ou mais vezes” e “uma ou mais vezes” são tão
comuns que há operadores específicos para elas:
O Fecho de Kleene, representado por “elevado a asterisco”,
aplica-se a um conjunto e significa “repetido zero ou mais vezes”.
Exemplo 1:
L = {s}∗
significa:
L = {λ, s, ss, sss, ssss, sssss, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 8 / 34
Fecho de Kleene
Exemplo 2:
L = {a, b, c}∗
é o mesmo que:
L =
{
p ∈ {a, b, c}n | n ≥ 0}
L = {λ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 9 / 34
Fecho de Kleene
Exemplo 3:
L = {0, 11}∗
As seguintes palavras fazem parte da linguagem L:
L = {λ, 0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Ou seja, sequências arbitrárias de 0 e 11→ Neste caso, 1 nunca
aparece sozinho!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 10 / 34
Fecho de Kleene
Exemplo 3:
L = {0, 11}∗
As seguintes palavras fazem parte da linguagem L:
L = {λ, 0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Ou seja, sequências arbitrárias de 0 e 11→ Neste caso, 1 nunca
aparece sozinho!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 10 / 34
Fecho de Kleene
É comum ver o Fecho de Kleene aplicado diretamente ao alfabeto:
L = Σ∗
significa “a linguagem contendo todas as palavras sobre o alfabeto
Σ”.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 11 / 34
Fecho Positivo de Kleene
O Fecho Positivo de Kleene, representado por “elevado a mais”,
também se aplica a um conjunto e significa “repetido uma ou mais
vezes”.
Exemplo 1:
L = {x}+
significa:
L = {x, xx, xxx, xxxx, xxxxx, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 12 / 34
Fecho Positivo de Kleene
Exemplo 2:
L = {0, 1}+
é o mesmo que:
L =
{
p ∈ {0, 1}n | n ≥ 1}
ou:
L =
{
p ∈ {0, 1}n | n > 0}
L = {0, 1}+ é uma maneira bem concisa de representar o conjunto
de números binários!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 13 / 34
Fecho Positivo de Kleene
Exemplo 2:
L = {0, 1}+
é o mesmo que:
L =
{
p ∈ {0, 1}n | n ≥ 1}
ou:
L =
{
p ∈ {0, 1}n | n > 0}
L = {0, 1}+ é uma maneira bem concisa de representar o conjunto
de números binários!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 13 / 34
Fecho Positivo de Kleene
Exemplo 3:
L = {0, 11}+
= {0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Veja que λ /∈ L.
Exemplo 4: No entanto, se definirmos:
L = {λ, 0, 11}+
então:
L = {λ, 0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 14 / 34
Fecho Positivo de Kleene
Exemplo 3:
L = {0, 11}+
= {0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Veja que λ /∈ L.
Exemplo 4: No entanto, se definirmos:
L = {λ, 0, 11}+
então:
L = {λ, 0, 11, 00, 011, 110, 1111, 000, 0011, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 14 / 34
Fecho Positivo de Kleene
Casos interessantes
Alguns casos interessantes:
I L = ∅, então L∗ = {λ};
I L = ∅, então L+ = ∅;
I L = {λ}, então L∗ = {λ};
I L = {λ}, então L+ = {λ}.
Em geral:
I λ ∈ L, então λ ∈ L+;
I λ /∈ L, então λ /∈ L+.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 15 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
ConcatenaçãoA concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas palavras é a palavra formada pelos
símbolos da primeira palavra seguidos dos símbolos da segunda
palavra.
A concatenação de duas palavras p e q é escrita pq.
Exemplos:
I p = 1 e q = 0, então pq = 10
I r = 1101 e s = 01, então rs = 110101
I m = pala e n = vra, então mn = palavra
I a = aaba e b = λ, então ab = aaba
I c = λ e d = λ, então cd = λ
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 16 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {a, b, c} e L2 = {x, y}, então L1L2 = {ax, ay, bx, by, cx, cy}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {a, b, c} e L2 = {x, y}, então L1L2 = {ax, ay, bx, by, cx, cy}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {a, b, c} e L2 = {x, y}, então L1L2 = {ax, ay, bx, by, cx, cy}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0, 00} e L2 = {λ, 1}, então L1L2 = {0, 01, 00, 001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0, 00} e L2 = {λ, 1}, então L1L2 = {0, 01, 00, 001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {λ, 0} e L2 = {λ, 0}, então L1L2 = {λ, 0, 00}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {λ, 0} e L2 = {λ, 0}, então L1L2 = {λ, 0, 00}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0}∗ e L2 = {λ, 1}, então
L1L2 = {λ, 1, 0, 01, 00, 001, 000, 0001, 0000, 00001, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0}∗ e L2 = {λ, 1}, então
L1L2 = {λ, 1, 0, 01, 00, 001, 000, 0001, 0000, 00001, . . .}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0}∗ e L2 = {1}∗, então
L1L2 = {λ, 1, 11, 111, . . . , 0, 01, 011, . . . , 00, 001, 0011, . . .}
“Sequência de zero ou mais 0s seguida de uma sequência de
zero ou mais 1s.”
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0}∗ e L2 = {1}∗, então
L1L2 = {λ, 1, 11, 111, . . . , 0, 01, 011, . . . , 00, 001, 0011, . . .}
“Sequência de zero ou mais 0s seguida de uma sequência de
zero ou mais 1s.”
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
A concatenação de duas linguagens L1 e L2 é a linguagem contendo
todas as concatenações de cada palavra de L1 com cada palavra de
L2.
Formalmente:
L1L2 = {p1p2} para cada p1 ∈ L1 e p2 ∈ L2
Exemplos:
I L1 = {0}∗ e L2 = {1}∗, então
L1L2 = {λ, 1, 11, 111, . . . , 0, 01, 011, . . . , 00, 001, 0011, . . .}
“Sequência de zero ou mais 0s seguida de uma sequência de
zero ou mais 1s.”
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 17 / 34
Concatenação
Se uma das linguagens concatenadas for vazia, o resultado também
é um conjunto vazio.
Exemplos:
I L1 = ∅ e L2 = {a, b, c}, então L1L2 = ∅
I L1 = {λ} e L2 = ∅, então L1L2 = ∅
I L1 = ∅ e L2 = {0, 1}∗, então L1L2 = ∅
I L1 = ∅ e L2 = ∅, então L1L2 = ∅
Cuidado! A linguagem ∅ é diferente da linguagem {λ}.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 18 / 34
Concatenação
Se uma das linguagens concatenadas for vazia, o resultado também
é um conjunto vazio.
Exemplos:
I L1 = ∅ e L2 = {a, b, c}, então L1L2 = ∅
I L1 = {λ} e L2 = ∅, então L1L2 = ∅
I L1 = ∅ e L2 = {0, 1}∗, então L1L2 = ∅
I L1 = ∅ e L2 = ∅, então L1L2 = ∅
Cuidado! A linguagem ∅ é diferente da linguagem {λ}.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 18 / 34
Concatenação
Se uma das linguagens concatenadas for vazia, o resultado também
é um conjunto vazio.
Exemplos:
I L1 = ∅ e L2 = {a, b, c}, então L1L2 = ∅
I L1 = {λ} e L2 = ∅, então L1L2 = ∅
I L1 = ∅ e L2 = {0, 1}∗, então L1L2 = ∅
I L1 = ∅ e L2 = ∅, então L1L2 = ∅
Cuidado! A linguagem ∅ é diferente da linguagem {λ}.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 18 / 34
Agrupamento
O agrupamento é uma forma conveniente de especificar que uma
operação de repetição se aplica sobre uma sequência de outras
operações.
O agrupamento é representado por um par de parênteses em torno
da sequência de símbolos: (sequência).
Vilar da CamaraNeto Teoria da Computação — Linguagens Formais: Operações 19 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L1 = ({0}{1})3 é a linguagem formada por três vezes a
concatenação {0}{1}: L1 = {010101}
I L2 = ({x}{x, y})2 é a linguagem formada por duas vezes a
concatenação {x}{x, y}: L2 = {xxxx, xxxy, xyxx, xyxy}
I L3 = ({a}{b})0 é a linguagem formada por zero vezes a
concatenação {a}{b}: L3 = {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 20 / 34
Agrupamento
Exemplos:
I L4 = ({a, b}{c, d})∗ é a linguagem formada pelo fecho de
Kleene sobre a concatenação {a, b}{c, d}:
L4 = {λ, ac, ad, bc, bd, acac, acad, acbc, acbd, adac, . . .}
Neste caso, pode-se considerar que L4 = {ac, ad, bc, bd}∗.
I E L5 = ({a, b}{c, d}+)∗?
L5 = {λ, ac, ad, acc, acd, . . . ,
bc, bd, bcc, bcd, . . . ,
acac, acacc, acacd, acaccc, . . . ,
accac, accac, accad, accad, . . .}
Sempre há uma sequência de bs e/ou cs após cada a e cada b!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 21 / 34
Agrupamento
Exemplos:
I L4 = ({a, b}{c, d})∗ é a linguagem formada pelo fecho de
Kleene sobre a concatenação {a, b}{c, d}:
L4 = {λ, ac, ad, bc, bd, acac, acad, acbc, acbd, adac, . . .}
Neste caso, pode-se considerar que L4 = {ac, ad, bc, bd}∗.
I E L5 = ({a, b}{c, d}+)∗?
L5 = {λ, ac, ad, acc, acd, . . . ,
bc, bd, bcc, bcd, . . . ,
acac, acacc, acacd, acaccc, . . . ,
accac, accac, accad, accad, . . .}
Sempre há uma sequência de bs e/ou cs após cada a e cada b!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 21 / 34
Agrupamento
Exemplos:
I L4 = ({a, b}{c, d})∗ é a linguagem formada pelo fecho de
Kleene sobre a concatenação {a, b}{c, d}:
L4 = {λ, ac, ad, bc, bd, acac, acad, acbc, acbd, adac, . . .}
Neste caso, pode-se considerar que L4 = {ac, ad, bc, bd}∗.
I E L5 = ({a, b}{c, d}+)∗?
L5 = {λ, ac, ad, acc, acd, . . . ,
bc, bd, bcc, bcd, . . . ,
acac, acacc, acacd, acaccc, . . . ,
accac, accac, accad, accad, . . .}
Sempre há uma sequência de bs e/ou cs após cada a e cada b!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 21 / 34
Agrupamento
Exemplos:
I L4 = ({a, b}{c, d})∗ é a linguagem formada pelo fecho de
Kleene sobre a concatenação {a, b}{c, d}:
L4 = {λ, ac, ad, bc, bd, acac, acad, acbc, acbd, adac, . . .}
Neste caso, pode-se considerar que L4 = {ac, ad, bc, bd}∗.
I E L5 = ({a, b}{c, d}+)∗?
L5 = {λ, ac, ad, acc, acd, . . . ,
bc, bd, bcc, bcd, . . . ,
acac, acacc, acacd, acaccc, . . . ,
accac, accac, accad, accad, . . .}
Sempre há uma sequência de bs e/ou cs após cada a e cada b!
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 21 / 34
Demonstrações
As operações vistas até agora (repetição, fecho de Kleene,
concatenação e agrupamento) permitem formalizar linguagens
relativamente complexas.
Alguns exemplos serão apresentados a seguir. . .
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 22 / 34
Demonstrações
Demonstração 1: “Conjunto de todos os números binários com
tamanho par e cujos dígitos nas posições pares (2o dígito, 4o dígito,
etc.) são obrigatoriamente 0.”
Por exemplo, 0010 ou 1000101000101010, mas não 100100.
Uma solução:
L = ({0, 1}{0})+
Outra solução:
L = {00, 10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 23 / 34
Demonstrações
Demonstração 1: “Conjunto de todos os números binários com
tamanho par e cujos dígitos nas posições pares (2o dígito, 4o dígito,
etc.) são obrigatoriamente 0.”
Por exemplo, 0010 ou 1000101000101010, mas não 100100.
Uma solução:
L = ({0, 1}{0})+
Outra solução:
L = {00, 10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 23 / 34
Demonstrações
Demonstração 1: “Conjunto de todos os números binários com
tamanho par e cujos dígitos nas posições pares (2o dígito, 4o dígito,
etc.) são obrigatoriamente 0.”
Por exemplo, 0010 ou 1000101000101010, mas não 100100.
Uma solução:
L = ({0, 1}{0})+
Outra solução:
L = {00, 10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 23 / 34
Demonstrações
E se quisermos permitir que o tamanho seja ímpar?
Demonstração 2: “Conjunto de todos os números binários cujos
dígitos nas posições pares (2o dígito, 4o dígito, etc.) são
obrigatoriamente 0.”
Uma solução:
L = ({0, 1}{0})∗{0, 1, 00, 10}
Outra solução:
L = {00, 10}∗{0, 1, 00, 10}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 24 / 34
Demonstrações
E se quisermos permitir que o tamanho seja ímpar?
Demonstração 2: “Conjunto de todos os números binários cujos
dígitos nas posições pares (2o dígito, 4o dígito, etc.) são
obrigatoriamente 0.”
Uma solução:
L = ({0, 1}{0})∗{0, 1, 00, 10}
Outra solução:
L = {00, 10}∗{0, 1, 00, 10}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 24 / 34
Demonstrações
E se quisermos permitir que o tamanho seja ímpar?
Demonstração 2: “Conjunto de todos os números binários cujos
dígitos nas posições pares (2o dígito, 4o dígito, etc.) são
obrigatoriamente 0.”
Uma solução:
L = ({0, 1}{0})∗{0, 1, 00, 10}
Outra solução:
L = {00, 10}∗{0, 1, 00, 10}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 24 / 34
Demonstrações
Demonstração 3: “Conjunto de todos os números binários que
contenham a sequência 0000.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 25 / 34
Demonstrações
Demonstração 3: “Conjunto de todos os números binários que
contenham a sequência 0000.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗
Vilar da Camara NetoTeoria da Computação — Linguagens Formais: Operações 25 / 34
Demonstrações
Demonstração 4: “Conjunto de todos os números binários que
contenham a sequência 0000 pelo menos três vezes.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗
Outra solução:
L = ({0, 1}∗{0000})3{0, 1}∗
Ainda outra solução:
L = {0, 1}∗({0000}{0, 1}∗)3
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 26 / 34
Demonstrações
Demonstração 4: “Conjunto de todos os números binários que
contenham a sequência 0000 pelo menos três vezes.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗
Outra solução:
L = ({0, 1}∗{0000})3{0, 1}∗
Ainda outra solução:
L = {0, 1}∗({0000}{0, 1}∗)3
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 26 / 34
Demonstrações
Demonstração 4: “Conjunto de todos os números binários que
contenham a sequência 0000 pelo menos três vezes.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗
Outra solução:
L = ({0, 1}∗{0000})3{0, 1}∗
Ainda outra solução:
L = {0, 1}∗({0000}{0, 1}∗)3
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 26 / 34
Demonstrações
Demonstração 4: “Conjunto de todos os números binários que
contenham a sequência 0000 pelo menos três vezes.”
Uma solução:
L = {0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗{0000}{0, 1}∗
Outra solução:
L = ({0, 1}∗{0000})3{0, 1}∗
Ainda outra solução:
L = {0, 1}∗({0000}{0, 1}∗)3
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 26 / 34
Demonstrações
Demonstração 5: “Conjunto de todos os números binários que não
contenham a sequência 0000.”
Se a palavra λ fizesse parte da linguagem, poderíamos escrever:
L = ({λ, 0, 00, 000}{1})∗{λ, 0, 00, 000}
Uma solução correta pode ser:
L = ({λ, 0, 00, 000}{1})∗{0, 1, 00, 01, 000, 001, 0001}
Ou:
L = {1, 01, 001, 0001}∗{0, 1, 00, 01, 000, 001, 0001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 27 / 34
Demonstrações
Demonstração 5: “Conjunto de todos os números binários que não
contenham a sequência 0000.”
Se a palavra λ fizesse parte da linguagem, poderíamos escrever:
L = ({λ, 0, 00, 000}{1})∗{λ, 0, 00, 000}
Uma solução correta pode ser:
L = ({λ, 0, 00, 000}{1})∗{0, 1, 00, 01, 000, 001, 0001}
Ou:
L = {1, 01, 001, 0001}∗{0, 1, 00, 01, 000, 001, 0001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 27 / 34
Demonstrações
Demonstração 5: “Conjunto de todos os números binários que não
contenham a sequência 0000.”
Se a palavra λ fizesse parte da linguagem, poderíamos escrever:
L = ({λ, 0, 00, 000}{1})∗{λ, 0, 00, 000}
Uma solução correta pode ser:
L = ({λ, 0, 00, 000}{1})∗{0, 1, 00, 01, 000, 001, 0001}
Ou:
L = {1, 01, 001, 0001}∗{0, 1, 00, 01, 000, 001, 0001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 27 / 34
Demonstrações
Demonstração 5: “Conjunto de todos os números binários que não
contenham a sequência 0000.”
Se a palavra λ fizesse parte da linguagem, poderíamos escrever:
L = ({λ, 0, 00, 000}{1})∗{λ, 0, 00, 000}
Uma solução correta pode ser:
L = ({λ, 0, 00, 000}{1})∗{0, 1, 00, 01, 000, 001, 0001}
Ou:
L = {1, 01, 001, 0001}∗{0, 1, 00, 01, 000, 001, 0001}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 27 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
União
A união de duas linguagens L1 e L2 é a linguagem que contém todas
as palavras de L1 e L2.
A união é representada pelo operador ∪.
Exemplos:
I L1 = {0, 1, 01} e L2 = {λ, 0, 11}, então
L1 ∪ L2 = {λ, 0, 1, 01, 11}
I L1 = {x}+ e L2 = {λ}, então L1 ∪ L2 = {x}∗
I L1 = {0, 1}∗{0} e L2 = {0, 1}∗{1}, então L1 ∪ L2 = {0, 1}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 28 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
IL1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Interseção
A interseção de duas linguagens L1 e L2 é a linguagem que contém
apenas as palavras comuns a L1 e L2.
A interseção é representada pelo operador ∩.
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 ∩ L2 = {λ, 1}
I L1 = {0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = ∅
I L1 = {λ, 0, 00, 000} e L2 = {λ, 01, 101}, então L1 ∩ L2 = {λ}
I L1 = {aa}∗ e L2 = {an | n ≤ 5}, então L1 ∩ L2 = {λ, aa, aaaa}
I L1 = {01}∗ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {λ, 01}
I L1 = {01}+ e L2 = {0}∗{1}∗, então L1 ∩ L2 = {01}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 29 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
DiferençaA diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Diferença
A diferença entre as linguagens L1 e L2 é a linguagem que contém
apenas as palavras pertencentes a L1 e não pertencentes a L2.
A diferença é representada pelo operador − (“menos”).
Exemplos:
I L1 = {λ, 0, 1, 01} e L2 = {λ, 1, 111}, então L1 − L2 = {0, 01}
I L1 = {λ, 0, 1, 10, 11} e L2 = {1}+, então L1 − L2 = {λ, 0, 10}
I L1 = {z}∗ e L2 = {zn | n ≤ 5}, então L1 − L2 = {zn | n > 5}
I L1 = {0}∗ e L2 = {0n | n é par}, então
L1 − L2 = {zn | n é ímpar}
I L1 = {10}+ e L2 = {01}+, então L1 − L2 = L1
I L1 = {10}∗ e L2 = {01}∗, então L1 − L2 = {10}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 30 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representadopor uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Complemento
O complemento de uma linguagem L é a linguagem que contém
todas as palavras que não pertencem a L.
Em outras palavras, o complemento de L é igual a Σ∗ − L.
O complemento é representado por uma barra sobre a linguagem: L¯.
Exemplos:
I Σ = {a, b} e L = {a}∗, então L¯ = {a, b}∗{b}{a, b}∗
I Σ = {a, b} e L = {a}+, então L¯ = {a, b}∗{b}{a, b}∗ ∪ {λ}
I Σ = {0, 1} e L = {0, 1}∗{1}, então L¯ = {0, 1}∗{0} ∪ {λ}
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 31 / 34
Demonstrações
Demonstração 1: “A linguagem dos números inteiros é constituída
por todas as palavras sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -}
que obedeçam às seguintes regras:
I Possuem pelo menos um dígito (0–9);
I Podem opcionalmente começar com um hífen (-).”
Uma solução:
L = {λ, -}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 32 / 34
Demonstrações
Demonstração 1: “A linguagem dos números inteiros é constituída
por todas as palavras sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -}
que obedeçam às seguintes regras:
I Possuem pelo menos um dígito (0–9);
I Podem opcionalmente começar com um hífen (-).”
Uma solução:
L = {λ, -}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 32 / 34
Demonstrações
Demonstração 2: “A linguagem dos números é constituída por todas
as palavras sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ,, -} que
obedeçam às seguintes regras:
I Possuem pelo menos um dígito (0–9);
I Podem opcionalmente começar com um hífen (-);
I Possuem no máximo uma vírgula (,), desde que seja precedida
e seguida por pelo menos um dígito.”
Uma solução:
L ={λ, -}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+({λ} ∪ ({,}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+))
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 33 / 34
Demonstrações
Demonstração 2: “A linguagem dos números é constituída por todas
as palavras sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ,, -} que
obedeçam às seguintes regras:
I Possuem pelo menos um dígito (0–9);
I Podem opcionalmente começar com um hífen (-);
I Possuem no máximo uma vírgula (,), desde que seja precedida
e seguida por pelo menos um dígito.”
Uma solução:
L ={λ, -}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+({λ} ∪ ({,}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+))
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 33 / 34
Demonstrações
Demonstração 2: “A linguagem dos números é constituída por todas
as palavras sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ,, -} que
obedeçam às seguintes regras:
I Possuem pelo menos um dígito (0–9);
I Podem opcionalmente começar com um hífen (-);
I Possuem no máximo uma vírgula (,), desde que seja precedida
e seguida por pelo menos um dígito.”
Outra solução:
LD = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+
L = {λ, -}LD
({λ} ∪ ({,}LD))
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 33 / 34
Licença de uso
cbnd CC BY-NC-ND 3.0
Este documento é disponibilizado sob a licença Creative Commons
Attribution-NonCommercial-NoDerivs, versão 3.0. Basicamente, esta licença permite
que este documento seja copiado, distribuído e transmitido livremente, desde que
sob as seguintes condições:
b Atribuição: É necessário fazer a atribuição da obra, da maneira estabelecida pelo
autor ou licenciante (mas sem sugerir que este o apoia, ou que subscreve o seu
uso da obra);
n Uso Não Comercial: Não se pode usar esta obra para fins comerciais;
d Obras Derivadas Proibidas: Não se pode alterar ou transformar esta obra, nem
adaptá-la ou utilizá-la noutras obras.
A atribuição desta obra deve fazer referência ao endereço do site de origem:
http://prof.vilarneto.com.
Detalhes sobre esta licença de uso podem ser obtidas em
http://creativecommons.org/licenses/by-nc-nd/3.0/deed.pt.
Vilar da Camara Neto Teoria da Computação — Linguagens Formais: Operações 34 / 34