Seja
um alfabeto finito de não vazio. Descrever o que representam os seguintes itens:
(a)
: um símbolo do alfabeto
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
Passo 1
O enunciado faz parte da teoria de linguagens formais. Temos um alfabeto finito não vazio
e precisamos dizer o que representam as expressões envolvendo símbolos, cadeias (\emph{strings}), fecho de Kleene, linguagens e o conjunto das linguagens.
Passo 2
Para entender símbolos e cadeias de comprimento fixo:
-
significa que é um único símbolo (ou letra) do alfabeto . -
é o produto (concatenação) de três cópias de , ou seja, o conjunto de todas as cadeias de comprimento exatamente 3 formadas por símbolos de .
Passo 3
Para falar de fechos:
-
é o fecho de Kleene de , isto é, o conjunto de todas as cadeias (incluindo a cadeia vazia) formadas por símbolos de . -
é o fecho positivo de , ou seja, o conjunto de todas as cadeias de comprimento pelo menos 1 formadas por símbolos de . Em notação, , onde é a cadeia vazia.
Passo 4
Uma variável
indica que
é uma cadeia (string) qualquer sobre o alfabeto
; pode ser a cadeia vazia ou qualquer sequência finita de símbolos de
.
Passo 5
A expressão
diz que
é um subconjunto de
. Dizemos que
é uma linguagem formal sobre o alfabeto
, pois seleciona um conjunto de cadeias desse alfabeto.
Passo 6
Falando de conjuntos de linguagens:
-
é o conjunto de todas as partes (power set) de . Logo, cada elemento de é uma linguagem sobre . - Se tivéssemos
, então seria um subconjunto de , ou seja, um conjunto de símbolos do alfabeto (não uma linguagem de cadeias, mas apenas um \emph{sub-alfabeto}).
Resposta
(a)
é um símbolo (letra) do alfabeto.
(b) é o conjunto de todas as cadeias de comprimento exatamente 3 sobre
.
(c) é o fecho de Kleene de
: todas as cadeias finitas (incluindo a vazia) sobre
.
(d) significa que
é uma cadeia (string) qualquer sobre
.
(e) é o fecho positivo de
: todas as cadeias não vazias sobre
.
(f) indica que
é uma linguagem formal, isto é, um conjunto de cadeias sobre
.
(g) é o conjunto de todas as linguagens possíveis sobre
(todas as partes de
).
(h) significa que
é um subconjunto de
, ou seja, um conjunto de símbolos do alfabeto.
(b)
(c)
(d)
(e)
(f)
(g)
(h)