3
$\begingroup$

$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?

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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\}^*\}$.

$\endgroup$
3
  • $\begingroup$ So the regular expression would be (01)(0|1)*(10)? $\endgroup$
    – Mock
    Oct 8, 2018 at 6:40
  • $\begingroup$ yes . . . . . . . $\endgroup$
    – Bjørn Kjos-Hanssen
    Oct 8, 2018 at 6:41
  • $\begingroup$ I see, thank you! Will accept when the timer allows. $\endgroup$
    – Mock
    Oct 8, 2018 at 6:42
-6
$\begingroup$

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\}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .