PROBLEM 2 ( 6 marks) Write regular expressions 1 describing the following languages over the alphabet {0,1}. 1. The words containing 01 and ending with 00. 2. The words containing 10 and ending with 00 . 3. The words containing exactly one occurrence of 00 . Hint: (1+01) describes all binary words in which every 0 (if any) must be followed by a 1 . PROBLEM 3 (6 marks) The grammar BP =({()},,{S},{SSS(S)},S) generates the language of balanced parentheses, that is, words like () and (())(), but not ) and ((). 1. Use the rules of BP to generate the word ()()() . Show clearly all the steps of the generation. 2. Use the grammar BP as a guide to write a grammar that generates the language of two types of balanced parentheses such as ()\langle angle and (()). The alphabet in this case is {(),,,}. 3. Modify your grammar from 2 so that the empty word is not generated. PROBLEM 4 (6 marks) Write context-free grammars to describe (generate) the following languages over the alphabet {0,1}. 1. L1={ww ends with three consecutive 0 's }. 2. L2={ww contains at least one 0 and at least one 1}. 3. L3={ww contains exactly one occurrence of the substring 01}. 1 Of the mathematical type, not the UNIX ones