Timeline for Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 28, 2019 at 18:13 | comment | added | Yuval Filmus | You cannot prove that a language isn’t regular by showing that it has a nonregular subset. It just doesn’t follow. I gave you a counterexample to this technique. | |
| Oct 28, 2019 at 17:46 | comment | added | RandomPerfectHashFunction | Yes, that's another alway to think about it. It just works out for $0^*1^*$, since every regular language is also a CFL. But in general the union of two CFLs is another CFL, which need not be a regular language. | |
| Oct 28, 2019 at 12:30 | comment | added | Yuval Filmus | The point is that the union of $L_1$ and the new $L_2$ is the language $0^*1^*$, which is regular. | |
| Oct 28, 2019 at 12:24 | comment | added | RandomPerfectHashFunction | The $L_2$ stated above is with $i \gt j$. Proving non-regularity for the language $\{ 0^i1^j : i \ge j\} $ is trivial since it has the language $\{ 0^i1^j: i = j \} $ as its subset. | |
| Oct 28, 2019 at 7:35 | comment | added | Yuval Filmus | Try your argument on $L_2 = \{0^i1^j : i \ge j \}$. | |
| Oct 28, 2019 at 6:38 | history | answered | RandomPerfectHashFunction | CC BY-SA 4.0 |