Which of the following languages is regular? A. {ww^R | w in {0,1}*} B. {ww^R x | x,w in {0,1}*} C. {wxw^R | w,x in {0,1}*, |w| = |x|} D. {xww^R | x,w in {0,1}*, |x| = |w|}
GATE 2007 · Theory of Computation · Regular Language · medium
Answer: Option B is regular because with w=epsilon the language equals {0,1}* = Sigma*. Answer: B. {ww^R x | x,w in {0,1}*}
- Check Option B for regularity: Let w = epsilon (the empty string). Then ww^R = epsilon (since reverse of empty string is empty). Then the set {ww^R x | w=epsilon} = {epsilon * x | x in {0,1}*} = {0,1}* = Sigma*. Since the language contains ALL strings over {0,1} (every string s can be written as s = epsilon * epsilon * s with w=epsilon, x=s), L = Sigma*. Sigma* is trivially regular (accepted by a 1-state DFA that accepts everything).
- Verify Options A, C, D are not regular: A: {ww^R} is the even-length palindromes. By pumping lemma (take 0^p 1^p 1^p 0^p), it is non-regular. C: {wxw^R | |w|=|x|} — strings have length 3|w|. For w=0^p: the string is 0^p x 0^p where |x|=p, and we need 0^p to appear both at the start and reversed at the end. Pumping breaks this structure. Non-regular. D: {xww^R | |x|=|w|} — x is unconstrained but |x|=|w|, and ww^R is a palindrome suffix of length 2|w|. Total length = 3|w|. The palindrome suffix structure requires non-regular memory. Non-regular.