Timeline for Lower bound for number of nonterminals in a CFG
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2016 at 20:31 | history | tweeted | twitter.com/StackCompSci/status/683385071580110848 | ||
| Dec 31, 2015 at 18:37 | vote | accept | CaptainCodeman | ||
| Dec 31, 2015 at 18:30 | vote | accept | CaptainCodeman | ||
| Dec 31, 2015 at 18:37 | |||||
| Dec 31, 2015 at 13:35 | comment | added | CaptainCodeman | @D.W. Is there a relation between the number of states in the pushdown automata and the number of nonterminals in the grammar? | |
| Dec 31, 2015 at 12:28 | answer | added | Yuval Filmus | timeline score: 3 | |
| Dec 31, 2015 at 11:44 | comment | added | Raphael | Closely related question. Do you guys have the same exercise sheet? | |
| Dec 31, 2015 at 11:42 | comment | added | Raphael | That's an interesting complexity measure for context-free languages. Have you done some searching? This may have been studied in the past. | |
| Dec 31, 2015 at 11:41 | history | edited | Raphael |
edited tags; edited tags
|
|
| Dec 31, 2015 at 4:02 | comment | added | D.W.♦ | What have you tried? You just need to prove that there is no grammar with 1 nonterminal. What form can each rule in such a grammar have? (It's a very restricted form.) Try a case analysis on the different forms such a rule can have. Can you have a rule of the form $S ::= rhs$ where $rhs$ is a string that contains two or more instances of $S$? See also cstheory.stackexchange.com/q/32056/5038 and the questions linked there. | |
| Dec 31, 2015 at 2:12 | review | First posts | |||
| Dec 31, 2015 at 10:04 | |||||
| Dec 31, 2015 at 2:07 | history | asked | CaptainCodeman | CC BY-SA 3.0 |