whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.

given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \mathbb{N}\}$

$L_2=\{(01)^{n}0(10)^{n} |n \in \mathbb{N}\}$

The only difference between $L_1$ and $L_2$ is the $0$ in the middle. $L_1$ is non-regular but $L_2$ is .

In the appendix page in the workbook it's written that:the intuition used in L1 is that I need to remeber an infinite states, and then using the "Pumping Lemma" they disproved that it is regular. It also says that L2 is regular and it is possible to build a DFA for the language.

I am not looking for answers for how to solve this, just why this notion of "machine have to remember an infinite states" is not applicable to $L_2$ because it seems that in $L_2$ the machine needs to remember how many times $01$ appeared then after $0$ machine needs to repeat the same number of time for $10$.

I also use this webpage:https://www.geeksforgeeks.org/how-to-identify-if-a-language-is-regular-or-not/

A bit over year ago I asked about the statemnets written there and they told it is not fully reliable(theorem no. 5 : "concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.")

Why language is not regular

Before trying to draw a DFA or disaproving using pumping lemma I use these theorems, but as it seems it maybe unreliable.

The questios are: why L1 is regular and L2 is not(I understand that one can be described via dfa and the other is not, just why L2 is not supposed to remember an infinite states).

and if the link for "geeks for geeks" can be used, to help to decide if language is regular or not?(I know that the only way to determine is by building dfa or pumping lemma=> these are the only 2 ways I've so far as a student studied,but before wasting time in the exam for building "DFA" for non regular language I need some sort of "hunch" as to choosing to disaprove by pumping lemma or building a DFA).


This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.


$L_2 = 0(1010)^*$

| cite | improve this answer | |
  • $\begingroup$ Nice,clear answer. $\endgroup$ – vonbrand Feb 15 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.