Computer Sciences > GATE 2025 SET-1 > Regular Languages
Consider the following two languages over the alphabet {a, b}:
L1={αβα|α∈{a,b}+ AND β∈{a,b}+}
L2={αβα|α∈{a}+ AND β∈{a,b}+}
Which ONE of the following statements is CORRECT?
A
Both L1 and L2 are regular languages.
B
L1 is a regular language but L2 is not a regular language.
C
L1 is not a regular language but L2 is a regular language.
D
Neither L1 nor L2 is a regular language.

Correct : c

This question tests a very important concept in automata theory — whether a finite automaton can "remember" something about the beginning of a string to verify it at the end. Let''s look at both languages one by one.
L1 = {αβα | α ∈ {a,b}+, β ∈ {a,b}+}
Here, α can be any non-empty string over {a, b} — it could be "ab", "bba", "abba", anything. The condition is that the string must start and end with the exact same α, with some non-empty β sandwiched in between. The problem is that α can be arbitrarily long and can contain both a''s and b''s in any order. A finite automaton has no memory to store what α looked like at the start, so it has no way to verify that the ending matches. This is a classic case where the pumping lemma kicks in — L1 is not regular.
To see it intuitively, consider strings like "ab · x · ab" where x is anything. The machine must remember "ab" from the beginning and match it at the end — but since α can be any string of any length, no finite set of states can handle all possibilities.
L2 = {αβα | α ∈ {a}+, β ∈ {a,b}+}
Now α is restricted to {a}+, meaning α = ak for some k ≥ 1. So every string in L2 starts with one or more a''s, has some middle portion β over {a,b}, and ends with the same number of a''s. But here''s the key insight — since both α and β can contain a''s, the string as a whole just needs to start with at least one a and end with at least one a, with at least one character in between.
This simplifies beautifully. L2 is essentially the set of all strings over {a,b} that begin with an a and end with an a, with length at least 3. That''s perfectly describable with a regular expression like a(a+b)+a, and a DFA can easily accept it. So L2 is regular.
The contrast between L1 and L2 is a great example of how restricting the alphabet of a component can completely change the nature of a language. When α was over {a,b}, the matching requirement was too complex for a DFA. When α was restricted to just {a}, the matching collapsed into a simple boundary condition that any DFA can handle.

Similar Questions

Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
#859 MSQ
Which of the following languages is/are regular? L1 = {wxwR | w, x ∈ {a, b}* and |w|, |x| > 0}, wR is the reverse of string w. L2 = {anbm | m ≠ n and...
#1169 MCQ
Let L1 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (110)'s as (011)'s}. Let L2 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (000)'s as (111...
#1268 MCQ

Related Topics

regularity of languages GATE 2025 GATE CS 2025 Set-1 Q44 automata theory GATE alpha beta alpha language L1 not regular L2 regular pumping lemma GATE DFA finite automaton theory of computation GATE regular language prefix suffix match

Unique Visitor Count

Total Unique Visitors

Loading......