An entropy metric for regular grammar classification and learning with recurrent neural networks

Kaixuan Zhang, Qinglong Wang, C. Lee Giles

Research output: Contribution to journalArticlepeer-review


Recently, there has been a resurgence of formal language theory in deep learning research. However, most research focused on the more practical problems of attempting to represent symbolic knowledge by machine learning. In contrast, there has been limited research on exploring the fundamental connection between them. To obtain a better understanding of the internal structures of regular grammars and their corresponding complexity, we focus on categorizing regular grammars by using both theoretical analysis and empirical evidence. Specifically, motivated by the concentric ring representation, we relaxed the original order information and introduced an entropy metric for describing the complexity of different regular grammars. Based on the entropy metric, we categorized regular grammars into three disjoint subclasses: the polynomial, exponential and proportional classes. In addition, several classification theorems are provided for different representations of regular grammars. Our analysis was validated by examining the process of learning grammars with multiple recurrent neural networks. Our results show that as expected more complex grammars are generally more difficult to learn.

Original languageEnglish (US)
Article number127
Pages (from-to)1-19
Number of pages19
Issue number1
StatePublished - Feb 2021

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Mathematical Physics
  • Physics and Astronomy (miscellaneous)
  • Electrical and Electronic Engineering


Dive into the research topics of 'An entropy metric for regular grammar classification and learning with recurrent neural networks'. Together they form a unique fingerprint.

Cite this