8
votes
Accepted
Is this language a context-free language or not?
No, $L_1$ is not necessarily context-free.
For example, let $L=\{0^n1^{3n}\mid n\ge0\}$.
If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$.
So, $L_1=\{1^...
- 34.8k
5
votes
Is the set of languages satisfying the pumping lemma closed under concatenation?
Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and ...
- 270k
4
votes
$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma
When the alphabet is of size $4$ or more, it is easy to prove that $L_4$ is not regular using the pumping lemma. Given a pumping length $n$, let $s$ be a square-free word over $\{0,1,2\}$ of length $n$...
- 270k
3
votes
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.
Yes, we can.
...
- 1,055
3
votes
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
The negation of "pumpable" as described in the pumping lemma states:
for all n
exists w in L with |w| > n
for all...
exists...
for which...
You can ...
- 149
3
votes
Accepted
Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k < ...
- 23.9k
3
votes
Implication of the Pumping lemma
Yes, since we can let $i$ be 0. Every non-empty word $x\in L$ can be expressed as "$xx^0\epsilon$".
We can also let $i$ be 1. Every non-empty word $x\in L$ can be expressed as "$\...
- 34.8k
3
votes
Is this language a context-free language or not?
I do not think the linked question is relevant.
Consider the context-free language $L = \{a^n b^n c^m d^m \mid m,n\ge 0\}$.
Let us consider an example string, $uv = a^3 b^3 c^8 d^8 $.
Assuming $u$ and ...
- 27.7k
2
votes
Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*
Hint: words in $\{ww\mid w\in\{a,b\}^*\}$ have even length.
- 7,193
2
votes
Accepted
Show the pumping lemma is not a universal method for proving not context-free
Let the pumping length $p=6$.
Let $s=a^ib^jc^k\in L$, $|s|\ge p$.
There are three cases.
$i=\max(i,j,k)$. We will pump a part of $a^i$.
$3i\gt i+j+k=|s|\ge p=6$. So $i\ge3$.
Among three nonnegative ...
- 34.8k
2
votes
I require assistance in proving this language as not regular
First of all, the empty pump matters (in fact, sometimes the empty pump, e.g.
the case $i=0$ is the simplest way to prove the non-regularity). Thus, the third condition is actually "for all $i\...
- 565
2
votes
Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$
For $b$ and $c$ fixed, this is a regular language. A corresponding regular expression would be $a^b(a^c)^*$.
- 7,193
2
votes
Accepted
Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$
I think that the language is regular. Aside of counting $a$'s $b$ times, instead of thinking of counting $c$ times $d$ (counting a known number of times something unknown), we can think of counting $d$...
- 81
2
votes
How does Sipser's proof that $0^n1^n$ is not regular work?
If $x$ consists of $p-2$ zeros, $y$ is 0 and $z$ consists of $p$ ones, then $xyz$ is $0^{p-1}1^p$, not $0^p 1^p$. Hence, the particular partition you give is impossible. If $|xy| < p$, then $z$ ...
- 1,100
2
votes
Accepted
What exactly is pumping length in pumping lemma?
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by ...
- 1,100
2
votes
Accepted
Prove a stronger version of the pumping lemma for context-free languages
Proof Idea for the usual pumping lemma
Let $z$ be a very long string in $L$. A parse tree for $z$ is so tall that it must contain some long path from the start symbol at the root of the tree to
one of ...
- 34.8k
1
vote
Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
The language $L_1 = \{a^n b^m: n, m \ge 0, m \ge n\}$ is not regular. This can be proved using the pumping lemma.
By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$ ...
- 1,100
1
vote
What exactly is pumping length in pumping lemma?
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.
Your finite automata can ...
- 805
1
vote
What exactly is pumping length in pumping lemma?
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the ...
- 1,500
1
vote
Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q.
After processing $a^p$ you are in a state S that ...
- 25.4k
1
vote
How does Sipser's proof that $0^n1^n$ is not regular work?
With the way you split your string, $|z|$ is $p +1$ and not $p$. Then, $z$ will be $01^p$ and not $1^p$. And with this, the proof stated by Sipser still holds.
- 1,500
1
vote
Accepted
Context-free pumping lemma of $a^nb^n$
You picked a wrong decomposition. Similarly to the pumping lemma for regular languages, the pumping lemma for context-free languages states that for every context-free language $L$, there exists some ...
- 1,055
1
vote
Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
There is a bit of a confusion on the notations:
what is $P$? If it is the pumping length, then say it so;
what is $p$? Is it a typo and should be a $P$?
what are $x$ and $y$? Don't hesitate to remind ...
- 7,193
1
vote
Accepted
Argument as to why a word does not belong to a language (pumping lemma)
Another way to write your language is $\{x^n y^m \mid n \leq m\}$. You can see this by proving that every word in $D$ belongs to this set, and vice versa (details left to you).
This shows that if $q &...
- 270k
1
vote
Can a context-free Language have an infinite pumping length?
The pumping lemma for context-free languages states that if $L$ is context-free then there exists a constant $p$ such that each word $w \in L$ of length at least $p$ can be partitioned into $w = uxyzv$...
- 270k
1
vote
Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$
Simpler using Myhill-Nerode: Given a string $b^y$, $y ≥ 1$. Which is the longest string $c^z$ such that $b^y c^z$ is in L? The answer is different for every for every y, therefore a state machine must ...
- 25.4k
1
vote
When proving a set is not regular is it enough to prove a subset of it regular?
I think L is irregular. Let's assume it is. Then $\{ab\}^*$ has an irregular subset, but is clearly regular. On the other hand, L has an irregular subset (L itself) but is irregular. So you can't ...
- 25.4k
1
vote
Accepted
Problem with Understanding Pumping Lemma
The language considered is indeed regular, since it can be expressed as a regular expression $111(11)^*(00)^*$.
Your mistake is that in the decomposition $z = 1^a1^bw$, you CANNOT chose $b$ to be odd. ...
- 7,193
1
vote
Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular
The pumping length here is what you refer to with the variable $n$. (Usually but not always, the letter $p$ is used, but the name is not important as long as it is clear to you and your audience.)
The ...
- 1,055
1
vote
Can I solve pumping lemma for context free language proofs using examples?
There are very many flaws in this proof attempt, and I would not give marks for this.
First of all: $L$ is NOT context-free and the pumping lemma for context-free languages can only be used to prove ...
- 1,055
Only top scored, non community-wiki answers of a minimum length are eligible