⟸ Go Back ⟸
Exercise 2 (Homework 1).
(theory of languages, concatenation)

Concatenation – basic properties

Justify your answers to the following questions. All words and languages are taken over a fixed alphabet.

  1. Is the concatenation commutative? Does it hold xy=yx for all words x,y? Does it hold AB=BA for all languages A,B? Do your previous answers depend on the size of the alphabet?
  2. Is the concatenation associative? Does it hold that x(yz)=(xy)z for all words x,y,z? Does it hold that A(BC)=(AB)C for all languages A,B,C? Do your previous answers depend on the size of the alphabet?
  3. Does the cancellation law hold for concatenation of words? That is, does xy=xz imply y=z for all words x,y,z?
  4. Does the cancellation law hold for concatenation of languages? That is, does AB=AC imply B=C for all languages A,B,C? What if we additionally impose that A\neq \emptyset, does it hold now?
  5. Condition for a double equality. Given languages A,B,C,D such that A,B are non-empty, AB=CD, and all words in A and C have the same length, does it hold that A=C and B=D?
  6. Does concatenation of languages distribute over union? That is, for all languages A,B,C, does it hold that (A\cup B) C=AC\cup BC and A(B\cup C)=AB\cup AC? What if instead of “=” we only ask for “\subseteq” or “\supseteq”, does it hold now?
  7. Does concatenation of languages distribute over intersection? That is, does it hold that (A\cap B) C=AC\cap BC and A(B\cap C)=AB\cap AC for all languages A,B,C? What if instead of “=” we only ask for “\subseteq” or “\supseteq”, does it hold now?