A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
This work addresses a deficiency in bionic parsing models for natural language processing, enabling broader language coverage, though it appears incremental as it builds on prior Assembly Calculus frameworks.
The paper tackles the limitation of an existing natural language parser based on Assembly Calculus, which could not handle Kleene closures and was weaker than Finite Automata, by proposing a new bionic parser that integrates Recurrent and Stack Circuits to parse all regular and Dyck languages, and formally proves it is equivalent to a Pushdown Automaton for parsing all Context-Free Languages.
Assembly Calculus (AC), proposed by Papadimitriou et al., aims to reproduce advanced cognitive functions through simulating neural activities, with several applications based on AC having been developed, including a natural language parser proposed by Mitropolsky et al. However, this parser lacks the ability to handle Kleene closures, preventing it from parsing all regular languages and rendering it weaker than Finite Automata (FA). In this paper, we propose a new bionic natural language parser (BNLP) based on AC and integrates two new biologically rational structures, Recurrent Circuit and Stack Circuit which are inspired by RNN and short-term memory mechanism. In contrast to the original parser, the BNLP can fully handle all regular languages and Dyck languages. Therefore, leveraging the Chomsky-Sch űtzenberger theorem, the BNLP which can parse all Context-Free Languages can be constructed. We also formally prove that for any PDA, a Parser Automaton corresponding to BNLP can always be formed, ensuring that BNLP has a description ability equal to that of PDA and addressing the deficiencies of the original parser.