Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
30 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
46 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
44 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
132 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
20 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
13 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
82 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 ...
0
votes
0answers
41 views

Is this language with fewer b's than twice the number of a's regular?

Is $\{a^{2n}b^m|0\leq m< n\}$ regular? The lecturer said it is not and referred to the pumping lemma but isn't 2 the pumping length? For every $n>m$ you can choose $u=\epsilon$, $v=aa$, $w$ the ...
0
votes
0answers
20 views

Choice of $x,y,z$ when applying the pumping lemma [duplicate]

I want to determine whether $$L=\big\{0^i \, 1^j \big| \,i,j \geq 1, \, i\neq j \big\}$$ is a regular language or not. Attempt: Let's assume that $L$ is regular. Then for $p=5$, the string $s \in ...
1
vote
1answer
16 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
53 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
51 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 ...
-1
votes
2answers
61 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
34 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
48 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
21 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 ...
0
votes
0answers
26 views

using pumping lemma to show a language is not CFL--a tricky points for me to clarify

I need feedback on a few things I did come across while proving a language is not CFL. $L=\{a^ib^jc^k | i>j \space and \space j=k\}$. This is not a CFL. And using pumping lemma like the following:...
1
vote
1answer
75 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
46 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
87 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
35 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
42 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.
0
votes
3answers
680 views

is this language regular and why pumping lemma doesn't work?

I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
1
vote
1answer
35 views

Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

I need help with proving the following language is not regular: $$ L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \} $$ My usual methods using pumping lemma are not getting me ...
1
vote
1answer
102 views

Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?

I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question Consider the ...
6
votes
3answers
2k views

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression ...
-1
votes
1answer
60 views

Prove {0^n OR 1^2n OR 2^3n | n >= 0} is not context free

How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n >= 0} is not context free This isnt the same language as {0^n1^2n2^3n | n >= 0} as this language the numbers need to be in order.
1
vote
1answer
38 views

Prove that $L^r$ is context free without alphabet

I'm stuck with this problem: Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$ is ...
6
votes
3answers
887 views

Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?
4
votes
1answer
51 views

General version of pumping lemma for regular languages, how many partitions to consider

The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$. The article on wikipedia says, that this ...
1
vote
0answers
56 views

Proving a language is not context-free using the pumping lemma

I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. ...
2
votes
1answer
62 views

Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.) Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language? This question ...
1
vote
1answer
82 views

I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular

Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$. So I applied the pumping lemma to see if it is non regular, ...
1
vote
1answer
61 views

Which word to pump in pumping lemma?

Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in ...
2
votes
2answers
92 views

Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular. I have not been able to solve this one: The set of ...
0
votes
0answers
63 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
0answers
11 views

How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]

This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
1
vote
1answer
30 views

Proving that language is regular or not [duplicate]

How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not: $\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$ I started with the ...
0
votes
1answer
123 views

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free. From my understanding, we want to prove that all 3 ...
0
votes
0answers
37 views

Pumping Lemma example explanation

The example is as follows: Problem: Show that $C = \{ a^{n!} \ | \ n \geq 0\}$ is not regular using the pumping lemma. PROOF BY CONTRADICTION: Assume $C$ is regular. By the pumping lemma for ...
2
votes
1answer
243 views

Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular

We have to prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular. Attempt: We assume that the language is regular. Thus it would satisfy ...
0
votes
0answers
43 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
1
vote
0answers
53 views

Proof that the language is not regular (Pumping Lemma) [closed]

I have to prove that the following language is not regular: $$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$ I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both ...
1
vote
1answer
35 views

Meaning of # in descriptions of languages

This is a very simple question, but I cannot find the answer anywhere, mostly because I don't know how else to ask about what I'm looking for. I have a homework assignment that has to do with pumping ...
2
votes
2answers
110 views

Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

Let $L$ a language over $X = \{a\}$ defined as follow : $$L = \{ a^{n!} \ | \ n \geq 0 \}$$ I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I ...
1
vote
1answer
58 views

Not able to prove non regularity using pumping lemma

$L$ = $0^p1^q0^p$. Where $p, q \geq 0$ Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$ So how do I prove it to be non ...
0
votes
1answer
34 views

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.
0
votes
0answers
54 views

Show that this language is not regular by Pumping Lemma

Over the alphabet $\Sigma=\{a,b\}$, we define $$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$ I must show that this laguage is not regular using the pumping lemma. I guess I should ...
0
votes
1answer
148 views

Pumping-Lemma regular languages: Consider multiple cases?

The language $ L = \{ a^nb^mc^m : n,m \in \mathbb{N} \} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages: Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq ...
2
votes
2answers
647 views

Use the pumping lemma to show the language is not regular

I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation. Can anyone explain how I would do this problem: For any string $s$ in ...