On Panini and the Generative Capacity of Contextualized Replacement Systems

摘要

This paper re-examines the widely held belief that the formalism underlying the rule system propounded by the ancient Indian grammarian, Panini (ca. 450-350 BCE)， either anticipates or converges upon the same expressive power found in finite state control systems or the context-free languages that are used in programming language theory and computational linguistics. While there is indeed a striking but cosmetic resemblance to the contextualized rewriting systems used by modern morphologists and phonologists, a subtle difference in how rules are prevented from applying cyclically leads to a massive difference in generative capacity. The formalism behind Paninian grammar, in fact, generates string languages not even contained within any of the multiple-component tree-adjoining languages, MCTAL(k), for any k. There is ample evidence, nevertheless, that Panini's grammar itself judiciously avoided the potential pitfalls of this unconstrained formalism to articulate a large-coverage, but seemingly very tractable grammar of the Sanskrit language.