Analyses of the case studies for the efficiency of pumping lemma for the context-free languages
DOI:
https://doi.org/10.59380/crj.v1i1.2760Abstract
In this study, we investigated the pumping lemma for context-free languages and analyzed some case studies in terms of their efficiency. Pumping lemmas play an important role in formal language theory. Context-free languages (CFL) is the set of languages that can be defined by context-free grammars. Context-free grammars are used to define programming languages, natural language applications (such as grammar correctors), machine protocols and many others. The case studies are used to simplify the process analyses of the efficiency of pumping lemma for Context-Free Languages. To prove that a Language is Not Context-Free using pumping lemma for CFL, we created a guideline presented in the fourth section that contains a proposed algorithmic procedure. Pumping lemma for CFL is used to show the existence of non-context free languages. Insights and argumentations were provided in the end of the paper.
Keywords:
Context-Free Languages, Pumping lemma, Intelligent systems, Machine/deep learning, Data sciencesDownloads
References
-
Amar, V. G. Putzolu, R. (1965). Generalizations of regular events, Information and Control, 8, 1, 56–63. ⇒195, 196, 197
-
Amarilli, A., & Jeanmougin, M. (2012). A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata. ArXiv, abs/1207.2819.
-
Barthwal, A., Norrish, M. (2014). A mechanization of some context-free language theory in HOL4. Journal of Computer and System Sciences.
-
Bole, J. (2021). Formal languages and automata theory: introduction to abstract and theories of computation.
-
Pettorossi, A., & Proietti, M. (2017). Regularity of languages generated by non context-free grammars over a singleton terminal alphabet. arXiv: Formal Languages and Automata Theory.
-
Rawlings, J., Mayne, D. (2020). Model Predictive Control: Theory, Computation, and Design, Nob Hill Publishing; 2nd edition
-
Horváth, G., & Nagy, B. (2010). Pumping lemmas for linear and nonlinear context-free languages. ArXiv, abs/1012.0023.
-
Smith, T. (2013) On infinite words determined by L systems, in: Lecture Notes in Computer Science, vol. 8079, Springer, Berlin, Heidelberg, pp. 238-249.
-
Smith, T. (2014) On infinite words determined by indexed languages, in: Lecture Notes in Computer Science, vol. 8634, Springer, Berlin, Heidelberg, pp. 511-522.
References
Amar, V. G. Putzolu, R. (1965). Generalizations of regular events, Information and Control, 8, 1, 56–63. ⇒195, 196, 197
Amarilli, A., & Jeanmougin, M. (2012). A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata. ArXiv, abs/1207.2819.
Barthwal, A., Norrish, M. (2014). A mechanization of some context-free language theory in HOL4. Journal of Computer and System Sciences.
Bole, J. (2021). Formal languages and automata theory: introduction to abstract and theories of computation.
Pettorossi, A., & Proietti, M. (2017). Regularity of languages generated by non context-free grammars over a singleton terminal alphabet. arXiv: Formal Languages and Automata Theory.
Rawlings, J., Mayne, D. (2020). Model Predictive Control: Theory, Computation, and Design, Nob Hill Publishing; 2nd edition
Horváth, G., & Nagy, B. (2010). Pumping lemmas for linear and nonlinear context-free languages. ArXiv, abs/1012.0023.
Smith, T. (2013) On infinite words determined by L systems, in: Lecture Notes in Computer Science, vol. 8079, Springer, Berlin, Heidelberg, pp. 238-249.
Smith, T. (2014) On infinite words determined by indexed languages, in: Lecture Notes in Computer Science, vol. 8634, Springer, Berlin, Heidelberg, pp. 511-522.
Downloads
Published
How to Cite
Issue
Section
