Timeline for prove decidability and recognizability
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 5, 2014 at 8:11 | vote | accept | binamu | ||
| Dec 4, 2014 at 9:13 | comment | added | David Richerby | You have to show that it's the same as $L_1$ but I guess that was just a typo in your comment. You can't go as far as "If $L_1$ is recognizable but not decidable, $L_1\cap L_2$ is recognizable but not decidable", since $L_2$ might be the empty set, which is regular and which gives $L_1\cap L_2=\emptyset$, which is both recognizable and decidable. So the best you can do is that $L_1$ recognizable implies $L_1\cap L_2$ recognizable, and $L_1$ decidable implies $L_1\cap L_2$ decidable. | |
| Dec 4, 2014 at 9:03 | comment | added | binamu | In the problem, I have to prove that the decidability of the intersect is same as $L_2$. It means that if $L_2$ is recognizable but not decidable, then the intersection is also recognizable but not decidable. | |
| Dec 4, 2014 at 8:57 | comment | added | David Richerby | Any language taht is decidable is also recognizable so it's enough to look at the intersection of two recognizable languages. | |
| Dec 4, 2014 at 8:49 | comment | added | binamu | I know that intersection of two decidable is decidable and intersection of two recognizable is recognizable. What can we say about intersection of a decidable language and a recognizable language (which is not decidable)? | |
| Dec 4, 2014 at 8:43 | history | answered | David Richerby | CC BY-SA 3.0 |