meta user
network profile
| bio | website | informatics.sussex.ac.uk/… |
|---|---|---|
| location | London, United Kingdom | |
| age | ||
| visits | member for | 2 years, 2 months |
| seen | yesterday | |
| stats | profile views | 19 |
|
1d |
comment |
Career in Number Theory? Don't worry too much about this now, wait until you've near finishing your PhD. A good PhD qualifies you for many different careers if you are no longer interested in number theory. At this point, I suggest to become as good a mathematician as you can. |
|
May 14 |
awarded | Caucus |
|
Nov 6 |
awarded | Commentator |
|
Nov 6 |
comment |
Generating functions for context-free languages Thanks that's neat! Is this transformation of collapsing all terminals functorial in some category of CFGs (whatever that might be)? Anyway, as nice as this is, it doesn't really seem to give a handle on the original question whether we can compute the generating functions (for degrees of ambiguity or number of $n$-length strings), or its power-series coefficients easily. Would you happen to have any further ideas in this direction? |
|
Nov 2 |
comment |
Generating functions for context-free languages @ Hendirk Jan, I'm interested in either, I just thought unambiguous is simpler (and in the case or regular expressions gives rise to a simple inductive definition of generating functions). For unambiguous grammars the coefficients $a_n$ in $\Sigma_{n < \omega}a_n f_n$ are always 'binary', i.e. either 0 or 1. Is there a systematic relationship between such binary formal power series, and power series that count strings of size $n$? |
|
Nov 2 |
comment |
Generating functions for context-free languages @ Hendirk Jan. As far as I understand (not very much) Schuetzenberger does this: let $\Sigma$ be a finite alphabet, and $(f_n)_{n<\omega}$ and enumeration of $\Sigma^*$. Then he produces a formal power-series $\Sigma_{n<\omega}a_n f_n$ such that $a_n$ is the number of ways that $f_n$ can be generated by the CFG. So $a_n$ measures ambiguity. The formal power series is obtained by a limiting process. That makes it difficult to read off the generating function that counts the strings of size $n$. I wonder if somebody wrote down a more convenient way of counting strings of size $n$. |
|
Nov 1 |
revised |
Generating functions for context-free languages added 5 characters in body |
|
Oct 31 |
revised |
Generating functions for context-free languages added 6 characters in body |
|
Oct 30 |
comment |
Generating functions for context-free languages @ Rick Decker: the formulations of the Schuetzenberger-Chomsky theorem I have seen, including the Wikipedia article you've linked to, don't give you the sequence ($a_i$) of cardinalities, or the generating function. But I'm after is the generating function, so I can use it obtain just that sequence. Are you aware of Schuetzenberger-Chomsky variants that enable me to do this? |
|
Oct 30 |
awarded | Yearling |
|
Oct 30 |
revised |
Generating functions for context-free languages added 21 characters in body |
|
Oct 30 |
revised |
Generating functions for context-free languages added 22 characters in body; edited tags |
|
Oct 30 |
asked | Generating functions for context-free languages |
|
Oct 5 |
revised |
Disjoint Union of Subsets and Direct Sum of Subspaces (Clarify Explanation) added 1 characters in body |
|
Oct 4 |
revised |
Disjoint Union of Subsets and Direct Sum of Subspaces (Clarify Explanation) deleted 12 characters in body |
|
Oct 4 |
revised |
Disjoint Union of Subsets and Direct Sum of Subspaces (Clarify Explanation) edited body |
|
Oct 4 |
revised |
Disjoint Union of Subsets and Direct Sum of Subspaces (Clarify Explanation) added 373 characters in body |
|
Oct 4 |
awarded | Teacher |
|
Oct 4 |
answered | Disjoint Union of Subsets and Direct Sum of Subspaces (Clarify Explanation) |
|
Oct 3 |
accepted | Does every prime ideal in a ring arise as kernel of a homomorphism into $\mathbb{Z}$? |
