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.

0
votes
0answers
33 views

Prove language is non-regular using pumping lemma

I'm working through an exercise in Peter Linz's book at the end of chapter 4 and am completely stumped. I believe you have to somehow use complement of L but, I'm not sure. Any help would be ...
0
votes
2answers
33 views

Using pumping lemma to prove irregularity of regular language - what is my error? [duplicate]

I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong? L={ab}, ...
2
votes
2answers
16 views

Confused about 3rd rule of CFG pumping lemma

Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL) Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the ...
-1
votes
1answer
49 views

Show that the Language L is not regular (pumping lemma) [closed]

$L = \{cda^nb^n\mid n\in \Bbb N\} \cup \{a,b,d\}^*$ Assuming $L$ is regular then there exist a pumping length $n$ for $L$. Lets use w = $cda^nb^n$. Thus $w \in L$ and $|w| = 2n+2$ $\implies$ $|w| \...
0
votes
0answers
36 views

What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, and $...
1
vote
1answer
29 views

Closure properties of a non-regular language under complement? [duplicate]

Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language. But let's say if the complement of L1 is a ...
2
votes
1answer
21 views

Does |xy| ≤ p in the pumping lemma count for all i?

While learning about the pumping lemma, I came across the following question: Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, ...
3
votes
2answers
113 views

Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma

I have the following alphabet: $Σ = {0, 1, . . . , 9}$ and the Language $L$ defined as: $L = \{ abc | a + b = c\} $ where substrings $a$, $b$ and $c$ are interpreted as ordinary integers. My answer ...
0
votes
0answers
53 views

Pumping lemma — Is this enough to prove that the language L is not regular?

I have a language $L$: $$L = \{w : a^ib^j; i > j \}$$ I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly: $L$ Is assumed to be regular. A ...
2
votes
2answers
56 views

Pumping lemma occurrence of c > d

I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it. The alphabet is: $$ \Sigma = \{c, d\} $$ The language is: $$ A = \{z ...
0
votes
2answers
63 views

Proving that L is not regular using closure properties

I need to show that the following language is not regular. $$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$ There is also a hint that it cannot be ...
1
vote
1answer
69 views

Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b \}$ is not regular. I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
1answer
56 views

What is the importance of the condition “| xy | < p” in pumping lemma? [duplicate]

Let L be a language. w $\in$ L , and w could be broken in xyz. Then if L is regular, there exists a pumping length p such that: |y| $\gt$ 0 |xy| $\le$ p $\forall$ i $\ge$ 0, xy$^i$z $\in$ L I ...
4
votes
1answer
264 views

Irregularity of language of prefixes of decimal expansion of pi

Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$ Prove that Lπ is not DFA-recognizable. You may use the ...
0
votes
2answers
46 views

Regularity of a language contains more 1's than 0's

The language of all bitstrings with more 1s than 0s, i.e., $ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular. I know I should apply Pumping Lemma and the proof as well, what I cannot ...
0
votes
1answer
58 views

Confused about pumping lemma, What i'm missing? [duplicate]

When I apply pumping lemma on this language: ${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular. let ${n=4}$, then $w=010000$...
5
votes
4answers
112 views

Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the ...
0
votes
1answer
42 views

Is this language L context-free?

The language $$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written word x, is context-free. Can someone ...
1
vote
2answers
50 views

Pumping lemma for regular languages [duplicate]

I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $L$ is a regular language, then there exists a constant $n$ such that for ...
3
votes
2answers
37 views

Can the pumping lemma for context free languages be extended to any subword?

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
1
vote
1answer
75 views

Which word could I use for the Pumping Lemma proof?

I have the language $ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \...
1
vote
1answer
73 views

Pumping Lemma vs Myhill-Nerode [duplicate]

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much. Let us take the following as an example: $$ L = \{ a^n b^n \mid n \ge 0\} $$ ...
0
votes
0answers
74 views

Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]

Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved? Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
1
vote
1answer
38 views

Pumping Lemma on Language with subtracted length

My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given $$ L = \{ a^k b a^{m-...
0
votes
1answer
56 views

Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ In my opinion complement of the L language is $L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$ I choose to ...
0
votes
1answer
79 views

Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
1
vote
2answers
89 views

Is the language of words that contain a square regular or context-free? [duplicate]

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
80 views

Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?

$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
0
votes
1answer
214 views

Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's

The following question on the theory of computation is GATE 2019 CS question 24: For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
1
vote
2answers
56 views

Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n

The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
2
votes
1answer
78 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
1
vote
1answer
71 views

Which word could I use for the pumping lemma?

I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma. Task: Be $\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \...
2
votes
1answer
148 views

How to prove a language is not regular using the Pumping Lemma?

I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult. Task: Prove that $M = \left\{ a^...
0
votes
1answer
90 views

picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}

If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$ when i pick a word for the language, would it be correct if i pick any of these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^...
4
votes
1answer
149 views

Language that fulfills pumping lemma but is not in RE

I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given ...
0
votes
0answers
52 views

Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
0answers
35 views

contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]

Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
1
vote
3answers
102 views

Prove a^4n b^m is irregular using puming lemma

My assignment is to prove that the language $L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language. My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an ...
1
vote
1answer
44 views

What is the minimum pumping length of the union of two languages?

If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them? Does it differ if either of them contains just one string like 001?
1
vote
2answers
61 views

Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it. This is language $L$ which is introduced with grammar: $$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$ ...
1
vote
2answers
75 views

Justification for the pumping lemma of context free languages

I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those ...
0
votes
2answers
74 views

Several simple propositions about regular languages

(Originally posted on Math-Stackexchange) https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions Notation: $\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet $\...
0
votes
1answer
267 views

Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular

I'm having issues using the pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{...
1
vote
1answer
60 views

How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
-1
votes
1answer
53 views

Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
1
vote
1answer
243 views

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it. Question Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$...
1
vote
1answer
134 views

Pumping Lemma Question: About the cases for y in the xy^iz criterion

Problem statement: Let $\Sigma = \{a, b, c\}$, and consider the task of multiplication encoded in the language $L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$. Prove that L is not regular using the ...
3
votes
1answer
201 views

Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
1
vote
1answer
50 views

Is my pumping lemma proof correct? [duplicate]

Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular I'd like to check if my proof for this is correct. Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+...
0
votes
1answer
70 views

Use the pumping lemma to prove that the following language is not context free

Can anyone help with the following problem ? Let $B = \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$, use the pumping lemma to prove B is not context-free Thanks in advance.