Regular Approximation of Context-Free Grammars for Chinese Language

As parsing context-free grammars is time-consuming, converting the original grammars into approximated regular languages can reduce the complexity. Based on the approaches, the so-called recursive transition network (RTN, which is an -NFA) is the most adequate approximated algorithm. The refinement is parameter RTN, which is more adequate than the original RTN. The suggested parameter is 2. However, the parameter RTN requires large memories, which limits its role in practical applications.
In this thesis, we propose a refinement of the parameter RTN which can alleviate the memory requirement effectively. The refined RTN (called group RTN) utilizes the prosperities of Chinese. It classifies the terms into different groups. Based on the different groups of terms, we integrate similar states and transitions of RTN into one. Using this scheme, the memory requirement of the RTN method can be reduced considerably.