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
  • 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 ...
user avatar
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$...
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
  • 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 ...
user avatar
  • 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 < ...
user avatar
  • 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 "$\...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
  • 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)^*$.
user avatar
  • 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$...
user avatar
  • 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$ ...
user avatar
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
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 ...
user avatar
  • 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$ ...
user avatar
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
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 &...
user avatar
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$...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 1,055

Only top scored, non community-wiki answers of a minimum length are eligible