CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

On Pumping lemma for Regular and Context free Lan-guages and Ogdenís Lemma for Context free Lan-guages

by K. Bala Prakasa Rao, B. Venu Gopal, R. Kanaka Raju
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 39 - Number 10
Year of Publication: 2012
Authors: K. Bala Prakasa Rao, B. Venu Gopal, R. Kanaka Raju
10.5120/4860-7137

K. Bala Prakasa Rao, B. Venu Gopal, R. Kanaka Raju . On Pumping lemma for Regular and Context free Lan-guages and Ogdenís Lemma for Context free Lan-guages. International Journal of Computer Applications. 39, 10 ( February 2012), 53-59. DOI=10.5120/4860-7137

@article{ 10.5120/4860-7137,
author = { K. Bala Prakasa Rao, B. Venu Gopal, R. Kanaka Raju },
title = { On Pumping lemma for Regular and Context free Lan-guages and Ogdenís Lemma for Context free Lan-guages },
journal = { International Journal of Computer Applications },
issue_date = { February 2012 },
volume = { 39 },
number = { 10 },
month = { February },
year = { 2012 },
issn = { 0975-8887 },
pages = { 53-59 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume39/number10/4860-7137/ },
doi = { 10.5120/4860-7137 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:26:07.586705+05:30
%A K. Bala Prakasa Rao
%A B. Venu Gopal
%A R. Kanaka Raju
%T On Pumping lemma for Regular and Context free Lan-guages and Ogdenís Lemma for Context free Lan-guages
%J International Journal of Computer Applications
%@ 0975-8887
%V 39
%N 10
%P 53-59
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Although pumping lemma can be applied to prove that certain languages are not regular/not context free. If we give a language as an input to the pumping lemma, it proves that the given language is not regular. If we give some regular language as an input to the pumping lemma, it proves that the language is not regular. We know that the input is regular language, but pumping lemma proves it is not regular. Hence results a contradiction. This paper mainly deals with the study on pumping lemma for regular and context free languages.

References
  1. John E.Hopcraft, Jeffery D.Ullman, Automata theory and formal languages by Narosa publishing company.
  2. PeterLinz, An Introduction to formal languages and Automata theory by Narosa publishing company.
  3. Y, Bar-Hillel, M.Perles and E.Shamir,”On formal properties of simple phase-structured grammars”, Z.Phonetick, Sprachwiss, kommuniationsforch.14 (1961), pp.143-172.
  4. R.E.Steavns and J.Hartmanis,”Regularity-Preserving modifications of Regular Expressions”, In-formation and Control 6:1(1963), pp.55-69.
  5. J.I.Seiferas and R.Mcnaughton,”Regularity Preserv-ing modifications, “Theoretical Computer Science 2:2(1976), pp 147-154.
  6. N.Chomsky,”On “On Certain formal properties of grammars”, Information and Control 2:2(1959), pp.137-167.
  7. M.P.Schutzenberger,”On Context Free Languages and pushdown automata”, Information and Control 6:3(1963), pp.246-264.
  8. Ginsburg’s (1966), The Mathematical Theory of Con-text free Languages, New York: McGraw Hill.
  9. Kleene, SC (1956), Automata Studies, Princeton, NJ: Princeton University Press.
  10. Kosaraju, SC (1974),”Regularity Preserving func-tions”, SIGACT News 6:2, 16-17.
  11. Kosaraju, SC (1975),”Context Free Preserving func-tions”, Math.Systems.Theory, 9:3, 193-197.
  12. Parikh, RJ (1966),”On Context Free Languages”, Journal of ACM 13:4, 570-581.
  13. Stearns, RE (1967),”A Regularity test for Pushdown Machines”, Information Control, 11:3, 323-340.
  14. Wise, DS (1967),”A Strong Pumping Lemma for CFL”, Theory of Computer Science, 3:3, 359-370.
  15. Moret, BM (2002), Theory of Computation, Asia, Pearson Education.
  16. Wood, D (1987), Theory of Computation, New York, Harper and Row Publishers.
  17. Dharaneetharan, G.D.; Raj, V.B.; Devi, R.K,”An alternative approach of Pumping Lemma to prove a language to be non-regular “, ICRTIT, 2011, Page(s): 1078 – 1080.
Index Terms

Computer Science
Information Sciences

Keywords

Pumping lemma Ogden’s lemma Finite automata Push down automata Regular expression

Powered by PhDFocusTM