⟸ Go Back ⟸
Exercise 5 (Homework 1).
(theory of languages, reverse)

Reverse – basic properties

Justify your answers to the following questions.

  1. The reverse of the concatenation (1). Show that for any two words x,y, (xy)^R=y^Rx^R. Does the analogue property hold for languages? That is, given languages L_1,L_2, does it hold that (L_1L_2)^R=L_2^RL_1^R?
  2. The reverse of the concatenation (2). Is it true that, given two languages L_1,L_2 such that (L_1L_2)^R=L_1^R L_2^R, then necessarily L_1=L_2?
  3. Does the reverse distribute over union? That is, given languages L_1,L_2, does it hold that (L_1\cup L_2)^R=L_1^R\cup L_2^R?
  4. Does the reverse distribute over intersection? That is, given languages L_1,L_2, does it hold that (L_1\cap L_2)^R=L_1^R\cap L_2^R?
  5. Does taking the complement and the reverse of a language commute? That is, it is true that \overline{L}^R=\overline{L^R}?
  6. Does taking the Kleene star and the reverse of a language commute? That is, it is true that (L^*)^R=(L^R)^*?