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.
357
questions
0
votes
0answers
36 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
168 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
31 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
221 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
26 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
28 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
63 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
53 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
27 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
57 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
53 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
36 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
60 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
163 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
78 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
63 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
40 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
20 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
53 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
49 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
80 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
27 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
122 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
61 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
112 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
65 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
273 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
53 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
70 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
126 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
43 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
52 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
38 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
77 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
126 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
82 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
47 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
84 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
113 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
81 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
408 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
59 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
101 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
73 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
206 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^...
