{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:44:51Z","timestamp":1760233491082,"version":"build-2065373602"},"reference-count":52,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:00:00Z","timestamp":1611014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/e23010127","type":"journal-article","created":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T11:39:55Z","timestamp":1611056395000},"page":"127","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4957-5289","authenticated-orcid":false,"given":"Kaixuan","family":"Zhang","sequence":"first","affiliation":[{"name":"Information Sciences and Technology, Pennsylvania State University, University Park, PA 16802, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7265-0497","authenticated-orcid":false,"given":"Qinglong","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Building A2, Lane 55 Chuan He Road Zhangjiang, Pudong New District, Shanghai 200135, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1931-585X","authenticated-orcid":false,"given":"C. Lee","family":"Giles","sequence":"additional","affiliation":[{"name":"Information Sciences and Technology, Pennsylvania State University, University Park, PA 16802, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Chowdhary, K. (2020). Natural language processing. Fundamentals of Artificial Intelligence, Springer.","DOI":"10.1007\/978-81-322-3972-7"},{"key":"ref_2","unstructured":"Zettlemoyer, L., and Collins, M. (2007, January 28\u201330). Online learning of relaxed CCG grammars for parsing to logical form. Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), Prague, Czech Republic."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1109\/32.708567","article-title":"Describing software architecture styles using graph grammars","volume":"24","year":"1998","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_4","unstructured":"Wang, Q., Zhang, K., Liu, X., and Giles, C.L. (2019). Verification of recurrent neural networks through rule extraction. arXiv."},{"key":"ref_5","unstructured":"Parker, A.J., Yancey, K.B., and Yancey, M.P. (2016). Regular language distance and entropy. arXiv."},{"key":"ref_6","unstructured":"Avcu, E., Shibata, C., and Heinz, J. (2017). Subregular Complexity and Deep Learning. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1162\/neco_a_01289","article-title":"Shapley Homology: Topological Analysis of Sample Influence for Neural Networks","volume":"32","author":"Zhang","year":"2020","journal-title":"Neural Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Mikolov, T., Karafi\u00e1t, M., Burget, L., \u010cernock\u1ef3, J., and Khudanpur, S. (2010, January 26\u201330). Recurrent neural network based language model. Proceedings of the Eleventh Annual Conference of the International Speech Communication Association, Chiba, Japan.","DOI":"10.21437\/Interspeech.2010-343"},{"key":"ref_9","unstructured":"Weiss, G., Goldberg, Y., and Yahav, E. (2019, January 3\u201314). Learning deterministic weighted automata with queries and counterexamples. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Oliva, C., and Lago-Fern\u00e1ndez, L.F. (2019, January 12\u201314). Interpretability of recurrent neural networks trained on regular languages. Proceedings of the International Work-Conference on Artificial Neural Networks, Gran Canaria, Spain.","DOI":"10.1007\/978-3-030-20518-8_2"},{"key":"ref_11","unstructured":"Marzouk, R., and de la Higuera, C. (2020). Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results. arXiv."},{"key":"ref_12","unstructured":"Marzouk, R. (2020). On Computability, Learnability and Extractability of Finite State Machines from Recurrent Neural Networks. arXiv."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Oliva, C., and Lago-Fern\u00e1ndez, L.F. (2019, January 17\u201319). On the interpretation of recurrent neural networks as finite state machines. Proceedings of the International Conference on Artificial Neural Networks, Munich, Germany.","DOI":"10.1007\/978-3-030-30487-4_25"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Huang, J.S. (1999). Lectures on Representation Theory, World Scientific.","DOI":"10.1142\/3988"},{"key":"ref_15","unstructured":"Watrous, R.L., and Kuhn, G.M. (December, January 30). Induction of finite-state automata using second-order recurrent networks. Proceedings of the Advances in Neural Information Processing Systems, Denver, CO, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1207\/s15516709cog1402_1","article-title":"Finding structure in time","volume":"14","author":"Elman","year":"1990","journal-title":"Cogn. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1109\/72.286928","article-title":"First-order versus second-order single-layer recurrent neural networks","volume":"5","author":"Goudreau","year":"1994","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_18","unstructured":"Hochreiter, S., Bengio, Y., Frasconi, P., and Schmidhuber, J. (2001). Gradient Flow in Recurrent Nets: The Difficulty of Learning Long-Term Dependencies, Wiley-IEEE Press."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cho, K., Van Merri\u00ebnboer, B., Bahdanau, D., and Bengio, Y. (2014, January 25). On the Properties of Neural Machine Translation: Encoder-Decoder Approaches. Proceedings of the SSST@EMNLP 2014, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation, Doha, Qatar.","DOI":"10.3115\/v1\/W14-4012"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1162\/neco.1992.4.3.393","article-title":"Learning and extracting finite state automata with second-order recurrent neural networks","volume":"4","author":"Giles","year":"1992","journal-title":"Neural Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1162\/neco.1996.8.4.675","article-title":"Stable encoding of large finite-state automata in recurrent neural networks with sigmoid discriminants","volume":"8","author":"Omlin","year":"1996","journal-title":"Neural Comput."},{"key":"ref_22","unstructured":"Rabusseau, G., Li, T., and Precup, D. (2019, January 16\u201318). Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning. AISTATS PMLR. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019), Naha, Okinawa, Japan."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Eyraud, R., and Ayache, S. (2020). Distillation of Weighted Automata from Recurrent Neural Networks using a Spectral Approach. arXiv.","DOI":"10.1007\/s10994-021-05948-1"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Okudono, T., Waga, M., Sekiyama, T., and Hasuo, I. (2020, January 7\u201312). Weighted automata extraction from recurrent neural networks via regression on state spaces. Proceedings of the AAAI Conference on Artificial Intelligence, New York, NY, USA.","DOI":"10.1609\/aaai.v34i04.5977"},{"key":"ref_25","unstructured":"Sutskever, I., Martens, J., and Hinton, G.E. (July, January 28). Generating Text with Recurrent Neural Networks. Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, DC, USA."},{"key":"ref_26","unstructured":"Wu, Y., Zhang, S., Zhang, Y., Bengio, Y., and Salakhutdinov, R. (2016, January 5\u201310). On Multiplicative Integration with Recurrent Neural Networks. Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain."},{"key":"ref_27","unstructured":"Hopcroft, J.E. (2008). Introduction to Automata Theory, Languages, and Computation, Pearson Education India."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Tomita, M. (1982, January 4\u20136). Dynamic construction of finite-state automata from examples using hill-climbing. Proceedings of the Fourth Annual Conference of the Cognitive Science Society, Ann Arbor, MI, USA.","DOI":"10.21236\/ADA120123"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"De la Higuera, C. (2010). Grammatical Inference: Learning Automata and Grammars, Cambridge University Press.","DOI":"10.1017\/CBO9781139194655"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/TNNLS.2015.2418323","article-title":"The kernel adaptive autoregressive-moving-average algorithm","volume":"27","author":"Li","year":"2015","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_31","unstructured":"Weiss, G., Goldberg, Y., and Yahav, E. (2017). Extracting automata from recurrent neural networks using queries and counterexamples. arXiv."},{"key":"ref_32","unstructured":"Hou, B., and Zhou, Z. (2018). Learning with Interpretable Structure from RNN. arXiv."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","article-title":"A logical calculus of the ideas immanent in nervous activity","volume":"5","author":"McCulloch","year":"1943","journal-title":"Bull. Math. Biophys."},{"key":"ref_34","first-page":"41","article-title":"Representation of events in nerve nets and finite automata","volume":"3","author":"Kleene","year":"1951","journal-title":"Autom. Stud."},{"key":"ref_35","unstructured":"Minsky, M. (1954). Neural Nets and the Brain Model Problem. [Ph.D. Thesis, Princeton Univ]."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1162\/neco.1989.1.3.372","article-title":"Finite state automata and simple recurrent networks","volume":"1","author":"Cleeremans","year":"1989","journal-title":"Neural Comput."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF00114844","article-title":"Distributed representations, simple recurrent networks, and grammatical structure","volume":"7","author":"Elman","year":"1991","journal-title":"Mach. Learn."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jcss.1995.1013","article-title":"On the computational power of neural nets","volume":"50","author":"Siegelmann","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1145\/235809.235811","article-title":"Constructing deterministic finite-state automata in recurrent neural networks","volume":"43","author":"Omlin","year":"1996","journal-title":"J. ACM"},{"key":"ref_40","unstructured":"Murdoch, W.J., and Szlam, A. (2017). Automatic Rule Extraction from Long Short Term Memory Networks. arXiv."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2568","DOI":"10.1162\/neco_a_01111","article-title":"An empirical evaluation of rule extraction from recurrent neural networks","volume":"30","author":"Wang","year":"2018","journal-title":"Neural Comput."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Huang, X., Kwiatkowska, M., Wang, S., and Wu, M. (2017, January 24\u201328). Safety verification of deep neural networks. Proceedings of the International Conference on Computer Aided Verification, Heidelberg, Germany.","DOI":"10.1007\/978-3-319-63387-9_1"},{"key":"ref_43","unstructured":"Eisner, J., Gall\u00e9, M., Heinz, J., Quattoni, A., and Rabusseau, G. (2019, January 2). Deep Learning and Formal Languages: Building Bridges. Proceedings of the Workshop on Deep Learning and Formal Languages, Building Bridges, Florence, Italy."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Lind, D., Marcus, B., Douglas, L., and Brian, M. (1995). An Introduction to Symbolic Dynamics and Coding, Cambridge University Press.","DOI":"10.1017\/CBO9780511626302"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Rogers, J., Heinz, J., Fero, M., Hurst, J., Lambert, D., and Wibel, S. (2013). Cognitive and Sub-Regular Complexity. Formal Grammar, Springer.","DOI":"10.1007\/978-3-642-39998-5_6"},{"key":"ref_46","unstructured":"Pin, J.\u00c9. (2010). Mathematical foundations of automata theory. Lecture Notes LIAFA, University Paris."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1051\/ita\/1997310504371","article-title":"Accurate computation of the relative entropy between stochastic regular grammars","volume":"31","author":"Carrasco","year":"1997","journal-title":"RAIRO-Theor. Inform. Appl."},{"key":"ref_48","unstructured":"Thollard, F., Dupont, P., and De La Higuera, C. (July, January 29). Probabilistic DFA inference using Kullback-Leibler divergence and minimality. Proceedings of the ICML, Stanford, CA, USA."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Suresh, A.T., Roark, B., Riley, M., and Schogol, V. (2019, January 23\u201325). Distilling weighted finite automata from arbitrary probabilistic models. Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing, Dresden, Germany.","DOI":"10.18653\/v1\/W19-3112"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Charalambides, C.A. (2018). Enumerative Combinatorics, CRC Press.","DOI":"10.1201\/9781315273112"},{"key":"ref_51","unstructured":"Tomita, M. (2020, January 14). Learning of Construction of Finite Automata from Examples Using Hill-Climbing. RR: Regular Set Recognizer. Technical Report, Carnegie-Mellon Univ Pittsburgh Pa Dept of Computer Science, Available online: https:\/\/apps.dtic.mil\/sti\/citations\/ADA120123."},{"key":"ref_52","first-page":"26","article-title":"Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude","volume":"4","author":"Tieleman","year":"2012","journal-title":"COURSERA Neural Netw. Mach. Learn."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/127\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:12:55Z","timestamp":1760159575000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,19]]},"references-count":52,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["e23010127"],"URL":"https:\/\/doi.org\/10.3390\/e23010127","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,1,19]]}}}