Semelhante ao uso nas linguagens regulares, também é possível utilizar operadores diretamente nos símbolos, pois, dada uma Linguagem L = {a}, se pode representá-la simplesmente por a. Desse modo, ao inserir o operador estrela, sobre a, por exemplo, teremos como resultado {ε, a, aa, aaa,...}. Tendo em vista o exposto, dadas as linguagens a seguir, marque a opção que representa uma linguagem que produz uma cadeia que começa e termina com o mesmo símbolo, considerando que ∑={a,b}:

Queremos uma linguagem (sobre o alfabeto $\Sigma=\{a,b\}$) que gere cadeias que começam e terminam com o mesmo símbolo.

• Cadeias que começam e terminam com a podem ser descritas por: $a\,\Sigma^*\,a$ (qualquer miolo, inclusive vazio, mas obrigatoriamente começa com $a$ e termina com $a$).
• Cadeias que começam e terminam com b podem ser descritas por: $b\,\Sigma^*\,b$.

Se tomarmos apenas $(a\,\Sigma^*\,a) \cup (b\,\Sigma^*\,b)$ (alternativa e), isso gera apenas cadeias de comprimento $\ge 2$ (por exemplo, $aa, aba, baab, bb$, etc.), mas não inclui as cadeias de comprimento 1: $a$ e $b$, que também “começam e terminam” com o mesmo símbolo (o único símbolo é ao mesmo tempo primeiro e último).

A alternativa d faz exatamente o ajuste necessário: [ (a\Sigma^*a) \cup (b\Sigma^*b) \cup a \cup b, ] isto é, inclui as cadeias com primeiro e último símbolo iguais de comprimento 2 ou mais, e também inclui explicitamente as cadeias unitárias $a$ e $b$.

Portanto, a opção que representa uma linguagem que produz cadeias que começam e terminam com o mesmo símbolo é a d.

Alternativa correta: (d).