L1={αβα|α∈{a,b}+ AND β∈{a,b}+}
L2={αβα|α∈{a}+ AND β∈{a,b}+}
Which ONE of the following statements is CORRECT?
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
Total Unique Visitors