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
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:
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.
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.
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.