Considerar a expressão regular a(a|b| c)^{*} a a\left|b(a|b| c)^{*} b b\right| c(a|b| c)^{*} c c sobre o alfabeto \{a, b, c\}. São exemplos de cadeias da linguagem representada por esta expressão regular:
(a) a a a, b b b e c c c
(b) a a a a, b b b a e a c c c
(c) a a b a, b b b b e c c c
(d) a b a a, b b c b e c c c b c c

Passo 1

O enunciado dá a expressão regular
a(a\mid b\mid c)^{*}aa \;\big|\; b(a\mid b\mid c)^{*}bb \;\big|\; c(a\mid b\mid c)^{*}cc
sobre o alfabeto \{a,b,c\} e pede qual das alternativas lista três cadeias que todas pertencem à linguagem definida por essa expressão. Vamos testar cada alternativa.

Passo 2

Observe que a expressão tem três ramos:
  1. a(a\mid b\mid c)^{*}aa gera todas as cadeias que começam com a, terminam com aa e têm qualquer (ou nenhum) símbolo no meio.
  2. b(a\mid b\mid c)^{*}bb gera todas as cadeias que começam com b, terminam com bb e têm qualquer símbolo no meio.
  3. c(a\mid b\mid c)^{*}cc gera todas as cadeias que começam com c, terminam com cc e têm qualquer símbolo no meio.
    Em particular, o caso mínimo (quando (a\mid b\mid c)^{*} é vazio) produz aaa, bbb e ccc.

Passo 3

Alternativa (a):
  • \(aaa) é gerada pelo primeiro ramo com estrela vazia.
  • \(bbb) é gerada pelo segundo ramo com estrela vazia.
  • \(ccc) é gerada pelo terceiro ramo com estrela vazia.
    Todas pertencem à linguagem.

Passo 4

Alternativa (b):
  • \(aaaa)) pertence (começa em a e acaba em aa.
  • \(bbba)) não pertence (começa em b mas não termina em bb.
  • \(accc)) não pertence (começa em a mas não termina em aa.
    Logo falha.

Passo 5

Alternativa (c):
  • \(aaba)) não pertence (não termina em aa.
  • \(bbbb)) pertence (começa em b, termina em bb.
  • \(ccc) pertence.
    Mas nem todas as três são aceitas.

Passo 6

Alternativa (d):
  • \(abaa)) pertence (começa em a, termina em aa.
  • \(bbcb)) não pertence (não termina em bb.
  • \(cccbcc)) pertence (começa em c, termina em cc.
    Faltam três cadeias aceitas.

Resposta

(a) \,aaa, \,bbb e \,ccc pertencem à linguagem.

Exercícios relacionados