Generating Sentences of CFL Based on Partition of CFG Production Set
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    In this paper, a method is presented to partition productions of CFG (context-f ree grammar). It divides production set into two parts. The derivation with prod uctions in one part will never terminate, while it must terminate rapidly with p roductions in the other part. It is proved that the procedure of generating sent ences of CFL (context-free language) is using productions in one part to make t he sentential form longer and more complex first, and then using productions in the other part to terminate the procedure. A general controllable method is atta ined for generating sentences of CFL with restricted length or depth. The time a nd space complexity for generating one sentence is O(r+n), where n is th e restricted length or depth of sentences and r is the number of productions in given CFG. The generating strategies for different conditions are also discu ssed.

    Reference
    1  Solomaa A. Formal Languages. London: Academic Press, 1973 2  Maurer P M. Generating test data with enhanced context-free grammars. IEEE S oftware, 1990,7(4):50~55 3  Dong Yun-mei. Collection of SAQ Report No.1~7. Technical Report, ISCAS-LCS -95-09. Laboratory of Computer Science, Institute of Software, The Chinese Aca demy of Sciences, 1995 4  Dong Yun-mei, Chen Hai-ming, Zhang Rui-ling. Collection of SAQ Report No.8 ~16. Technical Report, ISCAS-LCS-96-1. Laboratory of Computer Science, Insti tute of Software, The Chinese Academy of Sciences, 1996 5  Zhang Rui-ling. Research on an interactive model of concept acquisition [Ph .D. Thesis]. Institute of Software, The Chinese Academy of Sciences, 1999 6  Wetherell C S. Probabilistic languages: a review and some open questions. ACM Computing Surveys, 1980,12(4):361~379 7  Hickey T, Cohen J. Uniform random generation of strings in a context-free la nguage. SIAM Journal on Computing, 1983,12(4):64~6558 Dong Yun-mei. Recursive functions with define on CFL (I). SAQ Report No.22 , Technical Report, ISCAS-LCS-98-14, Laboratory of Computer Science, Institu te of Software, The Chinese Academy of Sciences, 1998
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王泓皓,董韫美.基于产生式集划分的上下文无关语言句子生成.软件学报,2000,11(8):1030-1034

Copy
Share
Article Metrics
  • Abstract:4580
  • PDF: 4598
  • HTML: 0
  • Cited by: 0
History
  • Received:January 17,2000
  • Revised:April 21,2000
You are the first2045328Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063