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.
364
questions
2
votes
0answers
53 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
0
votes
0answers
16 views
Regularity of language of words of prime length [duplicate]
Is the following language regular?
$$
L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}.
$$
I have to either provide a DFA (if the language is regular), or prove that it is not ...
0
votes
1answer
40 views
Using the pumping theorem to show that this language is not context-free
Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i*j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, here. ...
4
votes
1answer
106 views
How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
1
vote
2answers
53 views
Pumping Lemma with Prime Number [closed]
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$
$\text {Maybe we can say, that } w=a^{n}d^{...
0
votes
0answers
20 views
Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free
I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
1
vote
1answer
26 views
Are number of states in a NFA same as Pumping length?
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
1
vote
1answer
74 views
How can I prove the minimum pumping length of finite language?
Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the ...
0
votes
0answers
45 views
If L is a regular language, how to show that cut(L) is not necessarily regular? [duplicate]
Given that L is a regular language. How do I show that cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} is not necessarily regular?
My thought process is that this problem can be re-written as:
cut(L) = {...
0
votes
2answers
183 views
Is L2 = {a^n| n is a product of one or more primes} regular?
I am having a hard time proving the following with pumping lemma:
Is $L_2 = \{a^n \mid \text{$n$ is a product of one or more primes}\}$ regular?
Here's what I have so far:
Suppose $L$ is regular, ...
0
votes
0answers
36 views
Did I prove the language is not regular?
I am trying to prove the following language that is not regular.
I used Pumping Lemma proof and my proof goes as follows:
Assume that L is regular and let p be the constant of Pumping-Lemma.
This ...
2
votes
3answers
276 views
Is {a^n: n is a product of exactly two primes} regular?
I am struggling to prove the following question.
$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$
I feel like the language is not regular but I am having trouble proving it. I tried ...
0
votes
0answers
29 views
Proving a language is Not Regular without using Pumping Lemma? [duplicate]
I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction.
$$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$
I've seen a ...
0
votes
0answers
39 views
How to prove that L(G) is not regular by contradicting the pumping lemma?
I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
3
votes
1answer
111 views
Is Palindrome subset of a regular language regular?
Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
0
votes
0answers
58 views
Whether following language is linear or not?
I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$.
Now, I wanted to determine whether this language is linear or not.
So, I came up with this grammar:
$S \rightarrow A\thinspace|\thinspace Sc$
$A \...
0
votes
1answer
34 views
Whether the given language is a CFL or not?
Let $L$ be a language defined over $\Sigma = \left \{ a, b \right \}$ such that
$L = \left \{ x\#y \mid x,y \in \Sigma^*, \# \text { is a constant and } x \neq y \right \}$
State whether the language ...
0
votes
0answers
61 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
0
votes
0answers
25 views
Is there a language that pumps, but is not regular? [duplicate]
I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
2
votes
0answers
75 views
Pumping lemma for L = {a^i b^j c^k: i < j < k}
I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.
Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
...
1
vote
1answer
42 views
Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}
I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
2
votes
1answer
122 views
Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)
I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:
For any regular language L, there exists ...
3
votes
2answers
248 views
Converse of pumping lemma for regular expressions
I want to come up with a language that satisfies the pumping lemma while not being a regular expression.
I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
0
votes
1answer
22 views
Getting from one language to the other using closure properties(automata) [duplicate]
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
2
votes
2answers
96 views
Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?
$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
0
votes
1answer
68 views
$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma
How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
0
votes
2answers
44 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
22 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
54 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
61 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
108 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
35 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
130 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
62 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
58 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
138 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
75 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
70 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
406 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
61 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
77 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
142 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
49 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
55 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
43 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
81 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
179 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
93 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
2answers
73 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
59 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 ...
