search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.

Recent questions tagged pumping-lemma

0 votes
1 answer 15 views
@Praveen Saini @Lakshman Patel RJIT @Digvijay Pandey Just wanted to ask doubt, If the minimum pumping length of the language can be 0 for any language? I think it should not be as any string will either be accepted or rejected.
asked Jun 21 in Theory of Computation rish1602 9 points 15 views
1 vote
0 answers 27 views
The language is : number of zeroes=number of ones(which can be done by a deterministic Push down automata) say w=11101000 now we divide it to 5 parts u,v,w,x,y , where u=1 v=110 w=1 x=00 y=0 L=u.(v*i).w.(x*i).y such that i>=0 but when we put i=0 the ... . This shows that the language is not in L . But as the language can be done by a PDA , it should not have failed ,or do i not understand it ?
asked May 12 in Theory of Computation hari0943 9 points 27 views
0 votes
0 answers 13 views
How can I explain that this language- L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to formal languages and automata' but the explanation isn't ... it to me in an understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance
asked Jan 18 in Theory of Computation kirtipurohit 15 points 13 views
0 votes
0 answers 20 views
How to prove L={a ^n^2:n≥0} is not context free using Pumping Lemma?
asked Sep 28, 2020 in Theory of Computation Pathki Shivamsh 9 points 20 views
0 votes
2 answers 98 views
Is it necessary for the CFL string lenghts to be in AP if the alphabet is a singleton set?
asked Aug 21, 2020 in Theory of Computation xiuhan 13 points 98 views
1 vote
2 answers 64 views
Show that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear. I understand that a PDA can be constructed for this, but what I don't get is: can't we use the pumping lemma to show that the strings ... think they can all be handled this way such that $w_i$ won't be in $L$. But this language is context-free, so where am I going wrong with this?
asked Aug 16, 2020 in Theory of Computation pritishc 27 points 64 views
0 votes
0 answers 19 views
Came to read and also got to know as a shortcut about classification of a Language on the basis of the comparisons into CFL or CSL.Is it really the standard method or is it the short trick or just an ill-defined way of attempting a question. This post can be taken as a reference – https://gateoverflow.in/26952/%23toc
asked Jul 13, 2020 in Theory of Computation prajjwalsingh_11 15 points 19 views
0 votes
0 answers 24 views
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
asked Apr 18, 2020 in Theory of Computation admin 573 points 24 views
0 votes
0 answers 15 views
A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TRUE? $L$ is necessarily a regular language. $L$ is necessarily a context-free language, but not necessarily a regular language. $L$ is necessarily a non-regular language. None of the above
asked Apr 18, 2020 in Theory of Computation admin 573 points 15 views
To see more, click for the full list of questions or popular tags.
...