Qual é a expressão regular que representa a linguagem sobre o alfabeto
tal que a quantidade de símbolos
nas suas sentenças é ímpar?
(a)
(b)
(c)
(d)
(a)
(b)
(c)
(d)
Passo 1
O enunciado pede uma expressão regular sobre o alfabeto
que gere exatamente as cadeias com número de símbolos
ímpar. Vamos usar os operadores de concatenação e fecho de Kleene para controlar quantos
aparecem.
Passo 2
Observe que qualquer número ímpar de
pode ser escrito como um número par (inclusive zero) de
seguido de mais um
. Assim dividimos a construção em duas partes:
- Um bloco que gera um número par de
. - Um bloco que gera exatamente um
(o “extra”).
Passo 3
Um par de
(isto é, dois
) intercalados por quaisquer
pode ser escrito como
Se aplicamos Kleene sobre esse bloco,
obtemos todas as cadeias com
ocorrências de
.
Passo 4
Para tornar o total de
ímpar, concatenamos após os pares um último
também rodeado de
, ou seja
Portanto a expressão completa fica
que gera exatamente as cadeias com número de
ímpar.
Resposta
(c)