# Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $$L$$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$

My explanation and work:
I know that we can prove with pumping lemma that a language is not regular.
I know that if $$L_1 \subset L_2$$ and $$L_2$$ is regular, then $$L_1$$ maybe regular or not so in this example, $$0^n1^n \subset L$$ but we can't say that this language is not regular.
next, I think that $$L$$ is regular because grammar $$A$$ can produce anything but after a little try, I found that $$A = 0^*1^*$$ and $$110101$$ is not a part of language, so it can not be $$(1 | 0)^*$$ which is regular.
at this point, I don't know is it regular, or not. $$S$$ grammar can produce strings which has equal 0 and 1 at the start and end, but maybe $$A$$ grammar can produce something that make language regular.
Is it possible to help me? can you give me any idea?

### Idea (from comment):

if we say that $$L$$ is regular, then we get intersection of it and $$0^*1010101^*$$.
for accept a string in this language, there is two state.

1) not equal number of $$0$$ and $$1$$ at the start and end of string:
suppose number is form of $$0^n1010101^{n+k}$$ for $$k \gt 0$$ (we can prove same for $$0$$). use $$S \to 0S1$$ to create $$0$$ at the start and $$1$$ end, after some level we get to $$0^nS1^n$$ but we can't use any $$S \to 0S1$$ or $$S \to 1S0$$ anymore so we must use $$S \to AA$$ and $$A = 0^*1^*$$ and we can't match string. we couldn't construct it if we start with $$S \to AA$$. so $$L$$ can't produce this kind of strings.

2) equal number of $$0$$ and $$1$$ at the start and end of string:
now our string is form of $$0^n1010101^n$$ and we can construct it with only $$S \to 0S1|1S0$$.

so intersection of $$L$$ and $$0^*1010101^*$$ is $$0^n1010101^n$$ which is easy to prove that is not regular. so our hypothesis is not correct and $$L$$ is not regular.

Thanks for idea. Is it true?

• Hint: intersect your language with $0^*1010101^*$. (Simpler examples might be possible.) – Yuval Filmus Nov 11 '18 at 0:47
• When you say $\lambda$, did you mean $\epsilon$? – Daniel Martin Nov 11 '18 at 1:38
• Yes. $\lambda$ means $\epsilon$. – Amin Nov 11 '18 at 3:54
• I add a way. is it true? – Amin Nov 11 '18 at 4:57
• Yes, I think that this should work. – Yuval Filmus Nov 11 '18 at 7:09

Your grammar generates the following language: $$L = \{ w0^*1^*0^*1^*\bar{w}^R : w \in \{0,1\}^* \},$$ where $$\bar{w}$$ is obtained from $$w$$ by switching 0s and 1s. Consider now $$L' = L \cap 0^*1010101^*$$. It is not hard to check that $$L$$ contains all words of the form $$0^n1010101^n$$ (take $$w = 0^n1$$ and $$0101 \in 0^*1^*0^*1^*$$). Conversely, if $$0^n1010101^m \in L'$$ and $$n \neq m$$, say $$n > m$$, then the decomposition $$0^n1010101^m = wx\bar{w}^R$$, where $$x \in 0^*1^*0^*1^*$$, must satisfy that $$\bar{w}^R = 1^k$$ for some $$k \leq m$$; but then $$x = 0^{n-k}1010101^{m-k} \notin 0^*1^*0^*1^*$$. We conclude that $$L' := L \cap 0^*1010101^* = \{ 0^n1010101^n : n \geq 0 \}.$$ It is not hard to check that $$L'$$ is not regular (for example, the words $$0^n$$ are pairwise inequivalent), and so $$L$$ also isn't regular.
Note that for any positive integers $$n$$ and $$m$$, $$0^n1010101^m$$ is not in $$L$$ if $$m > n$$, and is in $$L$$ if $$n = m$$. (using your "1" and "2" statements)
Therefore, the strings $$0^{n}101010$$ for all positive integers $$n$$ are in distinct equivalence classes as used in the Myhill-Nerode theorem, and therefore $$L$$ is not regular.