1
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

You can shorten your reasoning in the "idea from the comments":

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.

$\endgroup$

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.