Toda linguagem definida sobre um alfabeto
é um subconjunto de
. Esta afirmação é:
(a) Sempre falsa
(b) Sempre verdadeira
(c) Verdadeira apenas para linguagens não vazias
(d) Depende de
(a) Sempre falsa
(b) Sempre verdadeira
(c) Verdadeira apenas para linguagens não vazias
(d) Depende de
Passo 1
O enunciado pergunta se “toda linguagem definida sobre um alfabeto
é um subconjunto de
”. Isso envolve o conteúdo de linguagens formais: definição de alfabeto, cadeias e linguagens sobre um alfabeto.
Passo 2
Por definição, dado um alfabeto
, a classe de todas as cadeias (strings) formadas por símbolos de
é
onde
(a cadeia vazia) e
são as cadeias de comprimento
.
Passo 3
Uma linguagem
sobre
é, por definição, qualquer conjunto de cadeias sobre
. Logo,
Essa definição vale inclusive para a linguagem vazia
, pois
. Não depende do alfabeto nem de
ser vazio ou não.
Passo 4
Como “linguagem sobre
” significa exatamente “subconjunto de
”, a afirmação é sempre verdadeira.
Resposta
(b) Sempre verdadeira