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.
425
questions
0
votes
1answer
17 views
Pumping Lemma Proof (Type of wcw language)
I have the language $L = \{ dkd\space |\space d \varepsilon ${a,b}*, $k\varepsilon ${a,b} } and i have to show that it's non-regular using the pumping lemma.
The structure of the language i think can ...
0
votes
2answers
45 views
Cardinality of sets and strings -> confused
I have a question regarding the cardinality of sets and strings.
If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted.
If $ \Sigma^+ $ is empty, the ...
1
vote
2answers
46 views
What is wrong with this proof that proves that 0*1* is not a regular language?
I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.
Exercise 1.30:
Describe the error ...
-3
votes
0answers
21 views
0
votes
1answer
46 views
Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free
I have a question about the pumping lemma for context-free languages.
I understand the conditions of the pumping lemma.
Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
1
vote
1answer
48 views
Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\...
1
vote
1answer
54 views
How to prove a language isn't necessarily regular? [duplicate]
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to ...
2
votes
0answers
31 views
Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?
In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
2
votes
2answers
91 views
Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?
For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make ...
1
vote
3answers
234 views
Pumping lemma: why x in ∣xy∣ ≤ p?
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the ...
1
vote
1answer
72 views
Is there a human-friendly version of the Pumping-Lemma?
I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the ...
1
vote
1answer
44 views
Using the pumping lemma for a specific language
Please help me with the following question:
Define the language LONGERB to be the set of strings over $\{a,b\}$ where the longest substring containing only $b$’s is strictly longer than the longest ...
0
votes
0answers
22 views
Need some guidance on CFG pumping lemma proof
I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something ...
0
votes
1answer
73 views
I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}
So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.
2
votes
2answers
47 views
Irregularity of $\{0^x1^y : y \nmid x\}$
The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.
How would one prove this using Pumping Lemma?
I thought about it ...
1
vote
1answer
44 views
Is this language based on the number of $a$'s of a word over alphabet ${a, b}$ context-free?
I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$.
I have this: By contradiction, ...
0
votes
1answer
38 views
How to check if a language is not regular?
I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "...
1
vote
2answers
91 views
Language of all even-length words with no 1's in left half
Consider the following language:
$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$
where $\Sigma_1 = \{0,1\}$.
I need to show that this is ...
1
vote
1answer
40 views
How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
1
vote
2answers
65 views
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there ...
0
votes
1answer
37 views
Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$
Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma.
I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
1
vote
2answers
38 views
Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma
I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (...
1
vote
1answer
35 views
Applying the Pumping Lemma to aspecific string
Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
1
vote
1answer
136 views
What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$
What is the length of the longest string ...
0
votes
0answers
48 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
36 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
86 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
74 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 ...
-1
votes
1answer
36 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
44 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
2answers
119 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
32 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
32 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
73 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
69 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 ...
1
vote
1answer
53 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
34 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
36 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
59 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
43 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
541 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
34 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
117 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
65 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
37 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
56 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
76 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
27 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 ...
