Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for pumping-lemma
49
votes
6
answers
1
GATE CSE 2019 | Question: 15
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$
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...
Arjun
33.9k
views
Arjun
asked
Feb 7, 2019
Theory of Computation
gatecse-2019
theory-of-computation
pumping-lemma
1-mark
+
–
0
votes
0
answers
2
Pumping Lemma
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and explain why pumping it leads to a contradiction. {aaabnan∣n≥0} {ww∣w∈Σ∗}
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...
jg662
67
views
jg662
asked
Feb 22
Theory of Computation
theory-of-computation
pumping-lemma
+
–
0
votes
0
answers
3
Pumping Lemma
If there is a w’ such that w’ ∉ L in the final step of pumping lemma, then L is not regular (Lemma fails) Can we conversely say for certain if L is not regular, then definitely there is a w’ ∉ L. Simply : Can there be a case where we have all w’ ∈ L and still language is not regular?
If there is a w’ such that w’ ∉ L in the final step of pumping lemma, then L is not regular (Lemma fails)Can we conversely say for certain if L is not regular, then...
Mrityudoot
133
views
Mrityudoot
asked
Nov 8, 2023
Theory of Computation
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
4
Theory Of Computation | Minimum Pumping Length | MPL
MSQ Consider the following languages and their MPL (Minimum Pumping Length) Which among these are TRUE: L1 = aa(b)* :: MPL(L1) = 3 L2 = aa(aa)* :: MPL(L2) = 2 L2 = aa(aa)* :: MPL(L2) = 3 L2 = aa(aa)* :: MPL(L2) = 4 L3 = aa(ab)* :: MPL(L3) = 4 L4 = aa(b)* + aad(c)* :: MPL(L4) = 4
MSQ Consider the following languages and their MPL (Minimum Pumping Length)Which among these are TRUE: L1 = aa(b)* :: MPL(L1) = 3 L2 = aa(aa)* :: MPL(L2) = 2 L2 = aa(aa)*...
Souvik33
667
views
Souvik33
asked
Jan 7, 2023
Theory of Computation
theory-of-computation
pumping-lemma
+
–
0
votes
1
answer
5
Pumping Lemma
If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =} How can I prove that L is not a regular language using pumping lemma and contradiction?
If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =}How can I prove that L is not a regular language using pumping lemma and contradiction?
shallowfalcon
424
views
shallowfalcon
asked
Oct 17, 2022
Theory of Computation
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
1
answer
6
#Self Doubt
L = {0^n 1^2n 0^n+m , n,m>=0} Is this Language CFL or non CFL? According to me we can write this as 0^n 1^n 1^n 0^n 0^m Then we will keep on pushing 0's and as and when we get 1 we keep on popping 0's, now once the stack is ... then on seeing any number of 0's we don't push anything and when we reach the end of the string we simply move to the final state. Is this logic correct?
L = {0^n 1^2n 0^n+m , n,m>=0}Is this Language CFL or non CFL?According to mewe can write this as 0^n 1^n 1^n 0^n 0^mThen we will keep on pushing 0’s and as and when we ...
Sunnidhya Roy
592
views
Sunnidhya Roy
asked
Dec 12, 2022
Theory of Computation
theory-of-computation
dcfl
pumping-lemma
context-free-language
+
–
1
votes
1
answer
7
Peter Linz Edition 4 Exercise 4.3 Question 1 (Page No. 122)
Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that, every $w ∈ L$ of length greater than $m$ can be decomposed as $w = xyz,$ with $|yz| ≤ m$ and $|y| ≥ 1,$ such that $xy^iz$ is in $L$ for all $i$.
Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that,every $w ∈ L$ of length greater than $m$ can be decomposed as $w = x...
Naveen Kumar 3
253
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
0
votes
1
answer
8
Self Doubt
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
tusharb
479
views
tusharb
asked
Jul 29, 2022
Theory of Computation
self-doubt
theory-of-computation
pumping-lemma
+
–
1
votes
1
answer
9
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b} if yes then why please explain
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}if yes then why please explain
sachin_27
1.3k
views
sachin_27
asked
Jun 1, 2022
Theory of Computation
theory-of-computation
regular-language
pumping-lemma
context-free-language
+
–
2
votes
2
answers
10
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?
Is the language L = {$a^nb^m : n = 2^m$} context-free?
Naveen Kumar 3
557
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
2
answers
11
Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\...
Rishi yadav
447
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
1
answer
12
Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prim...
Rishi yadav
333
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
1
answer
13
pumping length - TOC
What is meant by ‘pumping length’ and how can we find it?
What is meant by ‘pumping length’ and how can we find it?
atulcse
549
views
atulcse
asked
Jan 28, 2022
Theory of Computation
theory-of-computation
pumping-lemma
+
–
3
votes
2
answers
14
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 12
The logic of pumping lemma is a good example of the pigeon-hole principle the divide and conquer technique recursion iteration
The logic of pumping lemma is a good example ofthe pigeon-hole principlethe divide and conquer techniquerecursioniteration
admin
931
views
admin
asked
Apr 1, 2020
Theory of Computation
nielit2017oct-assistanta-cs
theory-of-computation
pumping-lemma
+
–
0
votes
1
answer
15
Michael Sipser Edition 3 Exercise 1 Question 30 (Page No. 88)
Describe the error in the following $ $proof$"$ that $0^{*}1^{*}$ is not a regular language. $($An error must exist because $0^{*}1^{*}$ is regular.$)$ The proof is by contradiction. Assume that $0^{*}1^{*}$ is regular ... example $1.73$ shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.
Describe the error in the following $“$proof$"$ that $0^{*}1^{*}$ is not a regular language. $($An error must exist because $0^{*}1^{*}$ is regular.$)$ The proof is by ...
admin
892
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
pumping-lemma
proof
+
–
29
votes
4
answers
16
GATE IT 2005 | Question: 40
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
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 TR...
Ishrat Jahan
14.8k
views
Ishrat Jahan
asked
Nov 3, 2014
Theory of Computation
gateit-2005
theory-of-computation
pumping-lemma
easy
+
–
27
votes
1
answer
17
Michael Sipser exercise
For each of the following languages, give the minimum pumping length and justify your answer. 0001* 0*1* 001 ∪ 0* 1* 0*1$^+$0$^+$1* ∪ 10*1 (01)* ε 1*01*01* 10(11*0)*0 1011 Σ*
For each of the following languages, give the minimum pumping length and justify your answer.0001* 0*1*001 ∪ 0* 1*0*1$^+$0$^+$1* ∪ 10*1(01)*ε1*01*01*10(11*0)*01011Σ...
KULDEEP SINGH 2
7.7k
views
KULDEEP SINGH 2
asked
Feb 11, 2019
Theory of Computation
pumping-lemma
minimum-pumping-length
+
–
4
votes
2
answers
18
Pumping Lemma
monty
2.5k
views
monty
asked
Oct 28, 2016
Theory of Computation
theory-of-computation
pumping-lemma
lemma
+
–
0
votes
1
answer
19
Peter Linz Edition 4 Exercise 4.3 Question 3 (Page No. 122)
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Naveen Kumar 3
325
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
1
votes
2
answers
20
Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
Naveen Kumar 3
480
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register