Linked Questions

2 votes
0 answers
116 views

Pumping a Language does not imply regular [duplicate]

I am currently studying the pumping lemma for regular languages and I am trying to come up with an example where even if the language can be pumped it is not regular. Which condition of the lemma ...
user1704040's user avatar
0 votes
0 answers
48 views

Is there a language that pumps, but is not regular? [duplicate]

I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
merhoo's user avatar
  • 111
0 votes
0 answers
30 views

Pumping lemma for non regular languages [duplicate]

I read that pumping lemma is sufficient condition to prove non regularity of languages but not necessary condition. I know the first part that it is sufficient is true but not able to understand why ...
Sagar P's user avatar
  • 319
19 votes
3 answers
9k views

Example of a non-context free language that nonetheless CAN be pumped?

So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
user2329564's user avatar
8 votes
3 answers
2k views

Physical significance of pumping length in pumping lemma

Would it be possible to explain the physical significance of pumping length $p$ in pumping lemma for regular languages? Somehow, the physical significance of pumping length $p$ in pumping lemma for ...
Masroor's user avatar
  • 357
6 votes
1 answer
7k views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
OiciTrap's user avatar
  • 171
0 votes
2 answers
2k views

Showing that a language satisfies the pumping lemma

I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma If L = {ambncndn | m,n >= 1 } Should I have n be the constant of the ...
user3295674's user avatar
0 votes
2 answers
1k 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 ...
Da Mike's user avatar
  • 243
4 votes
1 answer
570 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 ...
Yamahari's user avatar
  • 203
1 vote
1 answer
2k 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\} $$ ...
Isaac Michaan's user avatar
5 votes
2 answers
173 views

$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises. $L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
Nathaniel's user avatar
  • 15.8k
0 votes
0 answers
116 views

How do I prove a language is not regular using L′ = {a b^i c^i | i ≥ 0}?

I have just started my masters without any substantial experience in programming and I am struggling to understand certain concepts. I have been given the following language $$L = \{a^i b^j c^k \mid i,...
sofiatb's user avatar
1 vote
0 answers
38 views

Which non regular language meets the requirements for pumping lemma for regular languages?

I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
SmallBrainStudent's user avatar