Search code examples
mathalgebralanguage-theory

Proving language properties


I am taking a course on the formal foundations of programming, one of things we have covered is proving certain properties of languages, i have done most of the work, but I am stuck on these two questions, as I have no idea how to prove them.

they are as follows:

A ^ (B ^ C) = (A ^ B) ^ C (which I believe is the associative rule)

A ^ (B U C) = (A ^ B) U ( A ^ C) (Distribution rule)

In these examples i have used the ^ to mean concatenation


Solution

  • First

    A^B is all the words x such that there is v in A and w in B such that x = vw

    let's prove A^(B^C) is included into (A^B)^C

    The A^(B^C) is all the words x such that there is v in A and w in B^C such that x=vw

    and w = lm where l is in B and m is in C then x=vlm

    x=(vl)m =v(lm) since vl is in A^B qnd m is in C then x is in (A^B)^C.

    then A^(B^C) is included into (A^B)^C.

    Same proof for inverse inclusion

    then A^(B^C) =(A^B)^C

    Second:

    x in B U C if and only if x is in B or x is in C.

    first inclusion:

    if x in A ^ (B U C)

    then x = vw where v in A and w in B or C

    Then x is in A^B or A^C

    then x is in (A ^ B) U ( A ^ C)

    second inclusion

    if x is in (A ^ B) U ( A ^ C)

    then x = vw with v in A and w in B or x =vw with with v in A and w in C

    then since v is always is A

    then x = vw where v in A and w in B or C

    x in A ^ (B U C)

    Therefore A ^ (B U C) = (A ^ B) U ( A ^ C)