# Tag Info

Accepted

• 23.9k

• 565

### 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
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

### 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
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
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

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