Qual é a expressão regular que representa a linguagem sobre o alfabeto \{a, b\} tal que a quantidade de símbolos b nas suas sentenças é ímpar?
(a) \left(a^{*} b a^{*}\right)^{*} b a^{*} b a^{*}
(b) \left(a^{*} b\right)^{*} a^{*} b a^{*} b a^{*}
(c) \left(a^{*} b a^{*} b\right)^{*} a^{*} b a^{*}
(d) \left(a^{*} b a^{*} b\right)^{*}\left(a^{*} b a^{*}\right)^{*}

Passo 1

O enunciado pede uma expressão regular sobre o alfabeto \{a,b\} que gere exatamente as cadeias com número de símbolos b ímpar. Vamos usar os operadores de concatenação e fecho de Kleene para controlar quantos b aparecem.

Passo 2

Observe que qualquer número ímpar de b pode ser escrito como um número par (inclusive zero) de b seguido de mais um b. Assim dividimos a construção em duas partes:
  1. Um bloco que gera um número par de b.
  2. Um bloco que gera exatamente um b (o “extra”).

Passo 3

Um par de b (isto é, dois b) intercalados por quaisquer a pode ser escrito como
a^{*} b a^{*} b.
Se aplicamos Kleene sobre esse bloco,
\bigl(a^{*} b a^{*} b\bigr)^{*},
obtemos todas as cadeias com 0,2,4,\dots ocorrências de b.

Passo 4

Para tornar o total de b ímpar, concatenamos após os pares um último b também rodeado de a, ou seja
a^{*} b a^{*}.
Portanto a expressão completa fica
\bigl(a^{*} b a^{*} b\bigr)^{*}\;a^{*} b a^{*},
que gera exatamente as cadeias com número de b ímpar.

Resposta

(c) \bigl(a^{*} b a^{*} b\bigr)^{*} a^{*} b a^{*}

Exercícios relacionados