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.
