Question

3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonregular? • For a language that is regular, give a regular expression that defines it. • For a nonregular language, using the pumping lemma prove that it is not regular. (a) A = {d 2j+1c k+1 | j ≥ k ≥ 0} · {c r+2b 2s+3 | r ≥ 0 and s ≥ 0} (b) B = {a 2j+2b k+3c j+1 | j ≥ 1 and k ≥ 1} · {d m+3 | m ≥ 0} Above “·” stands for language concatenation. Hints: The languages A and B are each expressed as concatenation of two components. If one (or both) of the components is non-regular, this does not imply anything about the non-regularity of the concatenation. If trying to show that a language C is non-regular, we have to apply the pumping lemma to the entire language C (and not to the individual components of the concatenation). On the other hand, if trying to show that C is regular, we can find regular expressions for the two components separately and then use the concatenation operation.

Answer 1