自然语言的计算复杂性研究

30多年前,许国璋先生提出了自然语言的计算复杂性究竟有多大的问题,本文试图回答许先生提出的这个问题,讨论正则语法、上下文无关语法的计算复杂性,说明交叉系列依存结构的计算复杂性,以此作为对许国璋先生百年诞辰的纪念。