On Separations of LR(0)-Grammars by Two Types of Pumping Patterns

Authors: M. Plátek, F. Mráz, D. Pardubská, D. Průša, Jiří Šíma
Publication year: 2021
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Proceedings of the 21st Conference Information Technologies – Applications and Theory (ITAT 2021)
Projects: FoNeCo: Analytical Foundations of Neurocomputing
Bibliographic citation: PLÁTEK, M., MRÁZ, F., PARDUBSKÁ, D., PRŮŠA, D., ŠÍMA, Jiří. On Separations of LR(0)-Grammars by Two Types of Pumping Patterns. In: BREJOVÁ, B., CIENCIALOVÁ, L., HOLEŇA, M., MRÁZ, F., PARDUBSKÁ, D., PLÁTEK, M., VINAŘ, T., eds. Proceedings of the 21st Conference Information Technologies – Applications and Theory (ITAT 2021). Aachen: Technical University & CreateSpace Independent Publishing, 2021, S. 140-146. ISSN 1613-0073. Dostupné z: http://ceur-ws.org/Vol-2962/paper05.pdf
ID: 546279
Online record: View online record

Abstract

We present two types of pumping patterns that allow a total separation inside the class of LR(0)- grammars. Using the same type of pumping patterns, we obtain a total separation inside of linear LR(0)-grammars. This type of study has a long-term motivation from computational linguistics and the area of syntactic error localization. A recent motivation also comes from the field of formal models of neural networks.