New answers tagged

1 vote

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 ...
user avatar
0 votes

Which z should I pick?

We want to show that the language $L_2 = \{0^n: n=2^k, k \ge 0\}$ is nonregular. By way of contradiction, suppose $L_2$ is regular. Let $p$ be the pumping length. Let $z = 0^{2^p}$. Then, $z \in ...
user avatar
0 votes

Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

We want to show the language $L = \{0^{2^n}: n \ge 0\}$ is nonregular. By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$, called the pumping length, such that all ...
user avatar
1 vote

Prove that the language of regular expressions is not regular

Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character ...
user avatar
  • 4,611
0 votes

What exactly is pumping length in pumping lemma?

A regular language has a finite state machine, and therefore it has a finite state machine with a minimum number of states n. If we examine the first n letters of an input string, there are n+1 states ...
user avatar
  • 24.9k
1 vote
Accepted

How to prove ww^r is context free using pumping lemma for context free languages

The pumping lemma for context-free languages is used to prove that a given language is not a context-free language. There exists a PDA accepting the language $L = \{w w^r: w \in \{0,1\}\}$, and so $L$...
user avatar
0 votes

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$ ...
user avatar
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 ...
user avatar
  • 27.2k
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^...
user avatar
  • 33k
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 ...
user avatar
  • 785
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 ...
user avatar
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 ...
user avatar
  • 1,257
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 ...
user avatar
  • 24.9k
2 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 < ...
user avatar
  • 22.7k
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$ ...
user avatar
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.
user avatar
  • 1,257
0 votes

Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?

Yes, you can choose different strings of length at least $p$ (where $p$ is the constant given in the pumping lemma) than the one given in the resource; however, not all strings will help you complete ...
user avatar
0 votes

Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular

In your proof, you assume $p=3$. This would only prove that there does not exist a machine [a finite automata] with three states accepting the given language $A = \{0^n 1^n: n \ge 0\}$. To show the ...
user avatar
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. ...
user avatar
  • 966
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 ...
user avatar
  • 149

Top 50 recent answers are included