Questions tagged [pumping-lemma]
Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords. Make sure your question isn't covered by applying the techniques in https://cs.stackexchange.com/q/1031/755.
404
questions
0
votes
0answers
35 views
How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma
I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here.
We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to ...
0
votes
1answer
27 views
If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?
I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we ...
0
votes
2answers
81 views
How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?
I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.
If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
1
vote
1answer
56 views
Correct application of the CFL Pumping Lemma
I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...
0
votes
1answer
25 views
Use of pumping lemma for not regular languages. (Proof Verification)
$L=\{w \in \{0,1,a\}^* | \#_0(w) = \#_1(w) \}$
We show that L is not regular by pumping lemma.
We choose w=$0^p 1^p a$
|w| = 2p+1
Now |xy| has to be $\leq p$
So x and y could only contain zeros. And $...
0
votes
1answer
37 views
Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)
language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear ...
0
votes
1answer
47 views
How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?
$L = {a^n + b^m + a^{n+m}}$
This is the language I want to show is not regular.
Now my problem is to choose p correctly.
Can I just set it as p=2*(n+m) ?
That's the problem I am facing now.
Thanks for ...
0
votes
0answers
25 views
Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?
I have question where it asks:
Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2?
Here's what I've done, but I do reach a contradiction...
u=a^r
v=a^s
x=a^t b^N a^...
1
vote
1answer
26 views
Prove that the language is not regular through Myhill-Nerode Equivalence
The language is given by: $$L=\{a^nb^m|n<m\}$$
I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence.
Any help ...
0
votes
2answers
63 views
Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular
Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular.
Here is my try, I would really appreciate if someone could tell me if this is a correct proof.
Proof:
Lets assume L is regular. Then we ...
1
vote
2answers
61 views
Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?
For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
2
votes
1answer
42 views
Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should follow to prove
that the language is not regular?
Assume that the language is ...
0
votes
1answer
32 views
validation of a pumping lemma proof for regular languages
I have the following regular expression:
Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
32 views
Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma
I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
1
vote
1answer
43 views
Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $
I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:
$$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$
I ...
0
votes
1answer
26 views
What is Pumping length for Union of Regular languages?
This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant ...
0
votes
1answer
87 views
Minimum pumping length of (01)* [duplicate]
Michael Sipser offers the definition:
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 ...
0
votes
1answer
30 views
Pumping lemma for regular languages vs. Pumping lemma for context-free languages
How can I prove the next claim:
If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages?
(Without any pre-condition about the ...
0
votes
1answer
53 views
Is this language with prefix regular?
Is this language regular?
${w ā (a + b)ā : |u_{a}|>= 2009 Ā· |u_{b}|}$ for every non empty prefix $u$ of string $w$}
I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|&...
1
vote
2answers
42 views
Regular of language of all words of length 3
Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$
I think the above language is regular. A DFA can be used to determine the above language.
Am I correct? Is the above language regular?...
2
votes
1answer
33 views
Language of lists of words, not all of which are different, is not context-free
How do I prove that the following language isn't context-free using the pumping lemma?
$$
L=\{w_1\#w_2\#\dots\#w_k \colon k ā„ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\}
$$
I am having ...
1
vote
1answer
42 views
necessary and sufficient pumping lemma - bounded pumping variant
There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.
According to that lemma:
A language $L$ is regular iff $\exists k$, $\forall x\in ...
3
votes
1answer
41 views
Minimum pumping length of concatenation of two languages
there's this small part of my homework that I just can't figure out.
Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that
...
0
votes
2answers
26 views
Is the language of rectangular matrices in MATLAB-style syntax context free?
Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...
0
votes
1answer
22 views
When proving a set is not regular is it enough to prove a subset of it regular?
E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?
0
votes
1answer
15 views
Can we specify the pumping length while applying pumping lemma
In all the examples I have seen, the pumping length $p$ is not specified. The string is a pattern that somehow has the $p$. E.g. when proving $L=\{a^n b^n c^n | n \geq 0\}$ is not context free, we ...
1
vote
3answers
306 views
$a^*b^*c^* \setminus \{a^n b^n c^n | n ā„ 0\}$ is not regular using pumping lemma?
$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\...
1
vote
1answer
75 views
How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?
I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and ...
1
vote
0answers
24 views
$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$
I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me?
I alredy found an anwser to the Problem above (...
1
vote
2answers
45 views
How to show that Language is not Context Free?
There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the ...
0
votes
1answer
26 views
Language of words whose run lengths are all distinct
Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?
$$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $...
2
votes
2answers
38 views
Proving non-regular language using the pumping lemma
I would like to verify that the following language is not regular.
I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in ...
2
votes
3answers
117 views
An approach to determine whether language is regular or not?
I have the following problem. I need to determine whether this language is regular or not:
$L:= \{ w \in \Sigma^*: \forall \alpha ā \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$
$|w|_\...
-2
votes
2answers
205 views
Is the set of strings with equal number of 010ās and 101ās regular?
Let the language be defined over alphabet{0,1}.
Can you prove this by pumping down?
1
vote
1answer
48 views
Distinction between 2 languages.One is regular the other is not
whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.
given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \...
1
vote
2answers
107 views
Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
0
votes
0answers
43 views
Is this proof for pumping lemma legit?
Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular.
I used the pumping lemma as follow:
there exists $n\in \mathbb{N}$
$z=uvw$
$|uv|\leq n , |v|\geq1$
$uv^iw$ is a string in L, so ...
1
vote
1answer
167 views
Use the pumping lemma to show it's not regular
I just learned pumping lemma this week and got confused on this question.
B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Ī£$.
Hint: the sequence of Fibonacci numbers get increasingly further ...
1
vote
1answer
40 views
When does $p$ break the pumping lemma
I want to prove that $\{A^iB^jC^k \mid i=j \text{ or } j=k\}$ is a not a regular language using the pumping lemma.
I've found that the only way to obtain a contradiction is when $x \in A^*$, $y \in B^...
1
vote
1answer
54 views
Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I started by stating that:
$|w\bar{w}| =...
1
vote
3answers
142 views
Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular
I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your answers,...
2
votes
0answers
75 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
0
votes
0answers
16 views
Regularity of language of words of prime length [duplicate]
Is the following language regular?
$$
L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}.
$$
I have to either provide a DFA (if the language is regular), or prove that it is not ...
0
votes
1answer
63 views
Using the pumping theorem to show that this language is not context-free
Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, ...
4
votes
1answer
202 views
How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
1
vote
2answers
79 views
Pumping Lemma with Prime Number [closed]
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$
$\text {Maybe we can say, that } w=a^{n}d^{...
0
votes
0answers
30 views
Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free
I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
1
vote
1answer
98 views
Are number of states in a NFA same as Pumping length?
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
1
vote
1answer
234 views
How can I prove the minimum pumping length of finite language?
Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the ...
0
votes
0answers
46 views
If L is a regular language, how to show that cut(L) is not necessarily regular? [duplicate]
Given that L is a regular language. How do I show that cut(L) = {ac | abc ā L and |a| = |b| = |c|} is not necessarily regular?
My thought process is that this problem can be re-written as:
cut(L) = {...
