Register

Recent questions tagged pumping-lemma

121
views
0 answers
0 votes
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∈Σ∗}
User Avatar
173
views
0 answers
0 votes
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 ... there be a case where we have all w' ∈ L and still language is not regular?
User Avatar
824
views
0 answers
0 votes
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( ... ab)* :: MPL(L3) = 4 L4 = aa(b)* + aad(c)* :: MPL(L4) = 4
User Avatar
704
views
1 answers
0 votes
#Self Doubt
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 ... and when we reach the end of the string we simply move to the final state.Is this logic correct?
User Avatar
462
views
1 answers
0 votes
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?
User Avatar
519
views
1 answers
0 votes
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?
User Avatar
1.4k
views
1 answers
1 votes
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
User Avatar
650
views
1 answers
0 votes
pumping length - TOC
What is meant by ‘pumping length’ and how can we find it?
User Avatar
1.0k
views
2 answers
3 votes
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 12
The logic of pumping lemma is a good example ofthe pigeon-hole principlethe divide and conquer techniquerecursioniteration
User Avatar
762
views
0 answers
1 votes
Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are context-free.(a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*}(b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}.(C) $L=$ ... $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
User Avatar
662
views
2 answers
2 votes
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?
User Avatar
517
views
2 answers
1 votes
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.
User Avatar
575
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 2 Question 37 (Page No. 158)
Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a context-free ... z\in A,$v\neq\epsilon$ and $y\neq\epsilon,$and$\mid vxy\mid\leq k.$
User Avatar
1.8k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 2 Question 36 (Page No. 158)
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
User Avatar
1.3k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 2 Question 34 (Page No. 157)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ ... $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$
User Avatar
1.2k
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 2 Question 30 (Page No. 157)
Use the pumping lemma to show that the following languages are not context free$.$\{0^{n}1^{n}0^{n}1^{n}\mid n\geq 0\}$\{0^{n}\#0^{2n}\#0^{3n}\mid n\geq 0\}$\{w\#t\mid ... $\text{and}$ $ t_{i}=t_{j}$ $\text{ for some}$ $ i\neq j\}$
User Avatar
2.4k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 55 (Page No. 91)
The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length ... 1^{*}01^{*}01^{*}$10(11^{*}0)^{*}0$1011$\sum^{*}$
User Avatar
1.0k
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}|i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$Show that $F$ is not regular.Show ... for this value of $p.$Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.
User Avatar
972
views
1 answers
0 votes
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.$)$ ... cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.
User Avatar
3.2k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 29 (Page No. 88)
Use the pumping lemma to show that the following languages are not regular.$A_{1}=\{0^{n}1^{n}2^{n}|n\geq 0\}$ ... {(Here,}$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$
User Avatar
713
views
1 answers
0 votes
Self doubt:Pumping Lemma
How by Pumping Lemma we can prove that“context free grammar generate an infinite number of strings”and here what could be pumping length ?
User Avatar
Page: