GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 29

Question

Which of the following languages is/are regular? (Mark all the appropriate choices)

• A. $L = \{xww_R \mid w,x \in ({a+b})^+\}$
• B. $L = \{xww \mid w,x \in ({a+b})^*\}$
• C. $L = \{xwyw \mid w,x,y \in ({a+b})^+\}$
• D. $L = \{wxw_R\mid w,x \in ({a+b})^+\}$

Comments

For Option C:formal languages - Is $L = \{xwyw^r \mid x,w,y \in (a+b)^+ \}$ regular? - Mathematics Stack Exchange

---

option A was gem 💎

Answer 1

A - non determinism required to guess the start of $w$ as it cannot be empty string. $L$ is NCFL.

B - $x$ can include all strings in $\Sigma^*$ when $w = \epsilon.$ So, $L$ reduces to $(a+b)^*$ which is regular.

C - this is all strings of length at least $4$ over $\{a,b\}$ where the last letter repeats in between the second and third last. Regular

D - this is all $3$ length strings over $\{a,b\}$ starting and ending with same letter. Regular.

So, correct answer: B;C;D

Reference: https://gatecse.in/identify-the-class-of-a-given-language

Comments

What about the string aabba then?

---

okay Sir, got my mistake.

---

@gatecse sir, In option A can’t we just check the last 2 letters in the string and consider the rest all as a part of x?
That will leave us with just matching the second last and last character, making it regular.