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.

Filter by
Sorted by
Tagged with
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

Use pumping lemma (non regular language) to solve

{0^m 1^n 0^m | m,n >=0} vv^R :v: {a,b}*
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 ...

1
2 3 4 5
9