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 ...
