Analyses of the case studies for the efficiency of pumping lemma for the context-free languages

Authors

  • Majlinda Fetaji
  • Bekim Fetaji
  • Özcan Asilkan

DOI:

https://doi.org/10.59380/crj.v1i1.2760

Abstract

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 sciences

Downloads

Download data is not yet available.

Author Biographies

Majlinda Fetaji

South East European University, Faculty of Contemporary Science, Tetovo, Macedonia,

Bekim Fetaji

Mother Teresa University, Faculty of Informatics, Skopje, Macedonia

References

  1. Amar, V. G. Putzolu, R. (1965). Generalizations of regular events, Information and Control, 8, 1, 56–63. ⇒195, 196, 197

  2. Amarilli, A., & Jeanmougin, M. (2012). A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata. ArXiv, abs/1207.2819.

  3. Barthwal, A., Norrish, M. (2014). A mechanization of some context-free language theory in HOL4. Journal of Computer and System Sciences.

  4. Bole, J. (2021). Formal languages and automata theory: introduction to abstract and theories of computation.

  5. 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.

  6. Rawlings, J., Mayne, D. (2020). Model Predictive Control: Theory, Computation, and Design, Nob Hill Publishing; 2nd edition

  7. Horváth, G., & Nagy, B. (2010). Pumping lemmas for linear and nonlinear context-free languages. ArXiv, abs/1012.0023.

  8. Smith, T. (2013) On infinite words determined by L systems, in: Lecture Notes in Computer Science, vol. 8079, Springer, Berlin, Heidelberg, pp. 238-249.

  9. 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

2023-09-18

How to Cite

Fetaji, M., Fetaji, B., & Asilkan, Özcan. (2023). Analyses of the case studies for the efficiency of pumping lemma for the context-free languages. CRJ, 1(1), 9–15. https://doi.org/10.59380/crj.v1i1.2760

Issue

Section

Articles