Consider the languages L1 = phi (empty set) and L2 = {a}. Which one of the following represents L1* . L2*? A. {epsilon} B. {a}* C. phi D. L2 is regular.

GATE 2013 · Theory of Computation · Regular Language · medium

Answer: B. {a}*

1. Compute L1* = phi*: L1 = phi (empty language). phi^0 = {epsilon} by definition (zero concatenations of any language always gives {epsilon}). phi^k = phi for all k >= 1 (concatenating phi with anything gives phi). Therefore phi* = {epsilon} ∪ phi ∪ phi ∪ ... = {epsilon}.
2. Compute L2* = {a}*: {a}^0 = {epsilon}, {a}^1 = {a}, {a}^2 = {aa}, ... So {a}* = {a^n | n >= 0} = a* (the regular language of all strings of a's, including epsilon).
3. Compute L1* . L2* = {epsilon} . {a}*: L1*.L2* = {epsilon} . {a}* = {xy | x in {epsilon}, y in {a}*} = {epsilon.y | y in {a}*} = {y | y in {a}*} = {a}*. So L1*.L2* = {a}* = {epsilon, a, aa, aaa, ...}.
4. Match with answer options: Result is {a}*, which matches option B. Option A = {epsilon} would be the answer only if the operation were L1* alone or L1.L2*. Since L1*.L2* = {epsilon}.{a}* = {a}*, the answer is B.