Introducing the pushdown operator: a proposal to extend regular expressions to context-free languages
Resumo
This research proposes a new operator, called the pushdown operator, to be used in combination with the classical operators of regular expressions and aims to increase the denotational power of regular expressions in order to express the set of context-free languages. A literature review was conducted covering the main concepts related to formal languages and denotational formalisms, with an emphasis on context-free languages, which serve as a theoretical basis to support this research. Finally, the formal definition of the pushdown operator is presented, along with comparisons to the other two denotational formalisms of context-free languages found in the literature.Referências
Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2:113–124.
Gibney, D. and Thankachan, S. V. (2021). Text indexing for regular expression matching. Algorithms, 14(5):133.
Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.
HruŠa, V. (2021). Regular expressions with subpattern recursion. Master’s Thesis. Department of Theoretical Computer Science, Faculty of Information Technology CTU in Prague, Prague.
Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. Automata studies, 34:3–41.
Leiß, H. (1991). Towards kleene algebra with recursion. Lecture Notes in Computer Science, 626:242–256.
Menezes, P. B. (2000). Linguagens formais e autômatos. Sagra Luzzatto.
Sipser, M. F. (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology.
Sun, X., Mo, D., Wu, D., Ye, C., Yu, Q., Cui, J., and Zhong, H. (2023). Efficient regular expression matching over hybrid dictionary-based compressed data. Journal of Network and Computer Applications, 215:103635.
Takeshige, H., Matsumoto, S., and Kusumoto, S. (2022). Resem: Searching regular expression patterns with semantics and input/output examples. In International Conference on Product-Focused Software Process Improvement, pages 511–517. Springer.
Thompson, K. (1968). Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6):419–422.
Gibney, D. and Thankachan, S. V. (2021). Text indexing for regular expression matching. Algorithms, 14(5):133.
Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.
HruŠa, V. (2021). Regular expressions with subpattern recursion. Master’s Thesis. Department of Theoretical Computer Science, Faculty of Information Technology CTU in Prague, Prague.
Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. Automata studies, 34:3–41.
Leiß, H. (1991). Towards kleene algebra with recursion. Lecture Notes in Computer Science, 626:242–256.
Menezes, P. B. (2000). Linguagens formais e autômatos. Sagra Luzzatto.
Sipser, M. F. (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology.
Sun, X., Mo, D., Wu, D., Ye, C., Yu, Q., Cui, J., and Zhong, H. (2023). Efficient regular expression matching over hybrid dictionary-based compressed data. Journal of Network and Computer Applications, 215:103635.
Takeshige, H., Matsumoto, S., and Kusumoto, S. (2022). Resem: Searching regular expression patterns with semantics and input/output examples. In International Conference on Product-Focused Software Process Improvement, pages 511–517. Springer.
Thompson, K. (1968). Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6):419–422.
Publicado
20/07/2025
Como Citar
SILVA, Alexandre Tadeu Rossini da; OLIVEIRA, Guilherme da Cruz; SANTOS, Tanilson Dias dos.
Introducing the pushdown operator: a proposal to extend regular expressions to context-free languages. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 95-99.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.9085.
