Timeline for Is it decidable whether a given context free grammar generates an infinite number of strings?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2021 at 10:53 | comment | added | Shaull | By "variables" I only count the non-terminals. In Chomsky normal form, terminals are only derived in a single rule, with a single terminal at a time. As for the derivation tree: if you have a "string" somewhere in the tree, i.e. of the form S->A->B->S, then you can shorten it, since you just had S deriving S and nothing else. So I mean we start by getting rid of these. | |
| Jan 12, 2021 at 10:47 | comment | added | sprajagopal | "We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree." Could you please expand on this? Also, when you say $n$ variables in the grammar, that includes both terminals and nonterminals? If that is the case, then I'm guessing: there is a path from the root of this tree to some leaf and this path has a length of $|n + 2|$. Because this length is greater than $n$, there must be some variable that are repeated along the path (not necessarily one after the other). This particular repetition can be pumped. Am I getting it right? | |
| Feb 2, 2016 at 11:05 | vote | accept | kauray | ||
| Jan 31, 2016 at 16:48 | comment | added | Shaull | @vzn - I added a more formal statement. | |
| Jan 31, 2016 at 16:48 | history | edited | Shaull | CC BY-SA 3.0 |
added 131 characters in body
|
| Jan 31, 2016 at 16:41 | comment | added | vzn | sounds about right but it would be helpful to phrase this in mathematical language/ proof ie in the form "CFL has infinite strings iff ... [x]" | |
| Jan 31, 2016 at 10:19 | history | answered | Shaull | CC BY-SA 3.0 |