Toda linguagem definida sobre um alfabeto \Sigma é um subconjunto de \Sigma^{*}. Esta afirmação é:
(a) Sempre falsa
(b) Sempre verdadeira
(c) Verdadeira apenas para linguagens não vazias
(d) Depende de \Sigma

Passo 1

O enunciado pergunta se “toda linguagem definida sobre um alfabeto \Sigma é um subconjunto de \Sigma^*”. 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 \Sigma, a classe de todas as cadeias (strings) formadas por símbolos de \Sigma é
\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n,
onde \Sigma^0 = \{\varepsilon\} (a cadeia vazia) e \Sigma^n são as cadeias de comprimento n.

Passo 3

Uma linguagem L sobre \Sigma é, por definição, qualquer conjunto de cadeias sobre \Sigma. Logo,
L \subseteq \Sigma^*.
Essa definição vale inclusive para a linguagem vazia \varnothing, pois \varnothing\subseteq\Sigma^*. Não depende do alfabeto nem de L ser vazio ou não.

Passo 4

Como “linguagem sobre \Sigma” significa exatamente “subconjunto de \Sigma^*”, a afirmação é sempre verdadeira.

Resposta

(b) Sempre verdadeira

Exercícios relacionados