How Can The Following Language Possibly Be Regular?

66 Views Asked by At

$L =$ {$(01)^a$$x(10)^b$ | $a=b, b > 0, x∈${$0,1$}*}

This is a question where according to the key, yes, the language is regular, but no explanation is given. However, if $a=b$, then this can be rewritten as:

$L =$ {$(01)^n$$x(10)^n$ | $n > 0, x∈${$0,1$}*}

And $L =$ {$(01)^n$$(10)^n$ | $n > 0$} is a famous example of an expression which is NOT regular, so how on earth could inserting the $x$ in between the first two exponents allow it to be regular? I'm just not seeing any regular expression that could describe this, which is necessary for a language to be regular. What am I missing?

2

There are 2 best solutions below

3
On BEST ANSWER

Since $x$ can be anything, it can swallow most of the 01s and 10s. So it's the same as $\{01x10:x\in\{0,1\}^*\}$.

0
On

Hint: The intermediate symbol $x$ has no impact on the non-regularity of the language. The general method to show that a language is non-regular is the pumping lemma and this language is similar to $\{a^nb^n\mid n\geq 1\}$ or better $\{a^nxb^n\mid n\geq 1\}$.