Distributividade da concatenação sobre a união

A concatenação é distributiva em relação à união, tanto à esquerda quanto à direita:

$L_{1} (L_{2} \cup L_{3}) = L_{1} L_{2} \cup L_{1} L_{3}$ ,
$(L_{2} \cup L_{3}) L_{1} = L_{2} L_{1} \cup L_{3} L_{1}$ .

$L_{1} (L_{2} \cup L_{3})$ significa concatenar cada palavra de $L_{1}$ com cada palavra de $L_{2} \cup L_{3}$ . Isso é equivalente a concatenar $L_{1}$ com $L_{2}$ e $L_{1}$ com $L_{3}$ , unindo os resultados.

Similarmente, $(L_{2} \cup L_{3}) L_{1}$ distribui $L_{1}$ à direita de $L_{2}$ e $L_{3}$ .

Atenção

A ordem na concatenação é importante, e invertê-la altera o resultado final.

Exemplo

Se $L_{1} = {a}$ , $L_{2} = {b}$ , $L_{3} = {c}$ :

$L_{1} (L_{2} \cup L_{3}) = {a} {b, c} = {ab, a c}$ ,
$L_{1} L_{2} \cup L_{1} L_{3} = {ab} \cup {a c} = {ab, a c}$ ,
$(L_{2} \cup L_{3}) L_{1} = {b, c} {a} = {ba, c a}$ ,
$L_{2} L_{1} \cup L_{3} L_{1} = {ba} \cup {c a} = {ba, c a}$ .

NOTE

Essa propriedade é útil para decompor operações complexas em linguagens.

Referências

Aula 2 - Alfabetos palavras e linguagens

Notes

Explorer

Distributividade da concatenação sobre a união

Distributividade da concatenação sobre a união

Exemplo

Referências

Graph View

Table of Contents

Backlinks