(a) Show that if a language L is context-free then so are the following languages: L*...

Transcribed Image Text:

(a) Show that if a language L is context-free then so are the following languages: L* = ULK = {W₁... Wk | k≥ 0, w; € L for all i = 1,...,k}, k20 {wR|WEL}. LR = (Here w denotes the reversal of string w, i.e. w written backwards. (b) Show that if languages L₁ and L₂ are semidecidable, then so are the languages L₁ L₂ and L₁ L2= {w₁W₂ | W₁ E L₁, W₂ € L₂}. (a) Show that if a language L is context-free then so are the following languages: L* = ULK = {W₁... Wk | k≥ 0, w; € L for all i = 1,...,k}, k20 {wR|WEL}. LR = (Here w denotes the reversal of string w, i.e. w written backwards. (b) Show that if languages L₁ and L₂ are semidecidable, then so are the languages L₁ L₂ and L₁ L2= {w₁W₂ | W₁ E L₁, W₂ € L₂}.