f*********g
发帖数: 632 | 1 Chomsky–Schützenberger theorem. If L is a context-free language admitting
an unambiguous context-free grammar, and a_k := | L \ \cap \Sigma^k | is the
number of words of length k in L, then \sum_{k = 0}^\infty a_k x^k is a
power series over \mathbb{N} that is algebraic over \mathbb{Q}(x). |
f*********g
发帖数: 632 | 2 看到这个定理，我老郁闷了半天。
admitting
the
【在 f*********g 的大作中提到】
: Chomsky–Schützenberger theorem. If L is a context-free language admitting
: an unambiguous context-free grammar, and a_k := | L \ \cap \Sigma^k | is the
: number of words of length k in L, then \sum_{k = 0}^\infty a_k x^k is a
: power series over \mathbb{N} that is algebraic over \mathbb{Q}(x).
|
f*********g
发帖数: 632 | 3 We consider proper algebraic systems as defined in [7] and reprove via
Grobner bases algorithms that the quasiregular solution of such a system is
algebraic. In this context, the effective primary decomposition of a
polynomial ideal resp. the effective decomposition of an affine algebraic
variety into irreducible components are alternatives to the Kuich-Salomaa
elimination algorithm described in [7]. Both here applied decompositions are
based on the construction of a Grobner basis of an elimination ideal via
Buchberger's algorithm. We reprove then in a constructive way that the
generating function of each nonterminal of a context-free grammar is
algebraic and also that the generating function of a language, generated by
an unambiguous context-free grammar is algebraic (Chomsky-Schutzenberger [4]
).
2005年又一次证明。
admitting
the
【在 f*********g 的大作中提到】
: Chomsky–Schützenberger theorem. If L is a context-free language admitting
: an unambiguous context-free grammar, and a_k := | L \ \cap \Sigma^k | is the
: number of words of length k in L, then \sum_{k = 0}^\infty a_k x^k is a
: power series over \mathbb{N} that is algebraic over \mathbb{Q}(x).
|
n*****m
发帖数: 73 | 4 What's your point?
admitting
the
【在 f*********g 的大作中提到】
: Chomsky–Schützenberger theorem. If L is a context-free language admitting
: an unambiguous context-free grammar, and a_k := | L \ \cap \Sigma^k | is the
: number of words of length k in L, then \sum_{k = 0}^\infty a_k x^k is a
: power series over \mathbb{N} that is algebraic over \mathbb{Q}(x).
|
f*********g
发帖数: 632 | 5 感叹一下。呵呵。有看法也不说。呵呵。
【在 n*****m 的大作中提到】
: What's your point?
:
: admitting
: the
|
s*x
发帖数: 3328 | 6 到底有什么看法?
【在 f*********g 的大作中提到】
: 感叹一下。呵呵。有看法也不说。呵呵。
|
f*********g
发帖数: 632 | 7 没价值的看法会浪费大家时间，有价值的想法不会拿出来。呵呵。
【在 s*x 的大作中提到】
: 到底有什么看法?
|
f*********g
发帖数: 632 | 8 非常沮丧。
【在 f*********g 的大作中提到】
: 看到这个定理，我老郁闷了半天。
:
: admitting
: the
|
l******e
发帖数: 470 | 9 那你得涩啥呢。。
【在 f*********g 的大作中提到】
: 没价值的看法会浪费大家时间，有价值的想法不会拿出来。呵呵。
|
f*********g
发帖数: 632 | 10 滚。
【在 l******e 的大作中提到】
: 那你得涩啥呢。。
|
|
|
l******e
发帖数: 470 | 11 你这身打扮和我原来一样，可惜我的过期了
【在 f*********g 的大作中提到】
: 滚。
|
f*********g
发帖数: 632 | 12 再买啊，我就买了好几次了。真是。
买好衣服，拿好斧头，我们两个人对砍（侃）
【在 l******e 的大作中提到】
: 你这身打扮和我原来一样，可惜我的过期了
|
l******e
发帖数: 470 | 13 黑社会已经被我党缴灭了，你歇歇吧。
【在 f*********g 的大作中提到】
: 再买啊，我就买了好几次了。真是。
: 买好衣服，拿好斧头，我们两个人对砍（侃）
|
f*********g
发帖数: 632 | 14 看你的制服，像被招安了啊。
反正走黑路，灭了再发展吧。呵呵。
【在 l******e 的大作中提到】
: 黑社会已经被我党缴灭了，你歇歇吧。
|
f*********g
发帖数: 632 | 15 再顶上来。
admitting
the
【在 f*********g 的大作中提到】
: Chomsky–Schützenberger theorem. If L is a context-free language admitting
: an unambiguous context-free grammar, and a_k := | L \ \cap \Sigma^k | is the
: number of words of length k in L, then \sum_{k = 0}^\infty a_k x^k is a
: power series over \mathbb{N} that is algebraic over \mathbb{Q}(x).
|
l*******s
发帖数: 1258 | |
b******x
发帖数: 826 | 17 Groebner Basis数年以前上课学过，陈玉福讲的。 Formal language也是数年以前学过
。都忘得差不多了。没觉得过有什么联系。楼主是做数学的么。 |
f*********g
发帖数: 632 | 18 不是，
瞎混的。呵呵
【在 b******x 的大作中提到】
: Groebner Basis数年以前上课学过，陈玉福讲的。 Formal language也是数年以前学过
: 。都忘得差不多了。没觉得过有什么联系。楼主是做数学的么。
|
f*********g
发帖数: 632 | 19
~~~~~~~~~~~~~~~~~~~说明我和你（就是我们）的功底浅啊。上
面那篇文章是用Groebner Basis包括那一套算法等等证明这个定理。看到什么Church-
Rosser性质，就觉得跟lambda演算关系匪浅。再想想？
【在 b******x 的大作中提到】
: Groebner Basis数年以前上课学过，陈玉福讲的。 Formal language也是数年以前学过
: 。都忘得差不多了。没觉得过有什么联系。楼主是做数学的么。
|
