Timeline for Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 14, 2017 at 13:29 | vote | accept | Kishan Kumar | ||
| Oct 31, 2017 at 21:34 | answer | added | theyaoster | timeline score: 2 | |
| Oct 31, 2017 at 18:46 | comment | added | mikeazo | Let us continue this discussion in chat. | |
| Oct 31, 2017 at 18:35 | comment | added | Kishan Kumar | all instances of the problem must have an answer-yes or no | |
| Oct 31, 2017 at 18:26 | comment | added | mikeazo | Okay, lets go back a step. What does it mean for a problem to be decidable? | |
| Oct 31, 2017 at 18:08 | comment | added | Kishan Kumar | And telling the language would not help. Since we have to consider all languages(CFL) and not a particular one. | |
| Oct 31, 2017 at 18:07 | comment | added | Kishan Kumar | But you were asking whether the language is Turing recognizable | |
| Oct 31, 2017 at 18:06 | comment | added | mikeazo | A CFG generates strings according to the rules in the grammar. | |
| Oct 31, 2017 at 17:29 | comment | added | Kishan Kumar | @mikeazo What does a Context free grammar generates? | |
| Oct 31, 2017 at 17:27 | comment | added | mikeazo | What is the language? Is the language Turing-recognizable? Is the language co-Turing-recognizable? | |
| Oct 31, 2017 at 17:18 | history | asked | Kishan Kumar | CC BY-SA 3.0 |