Linked Questions
13 questions linked to/from Languages that satisfy the pumping lemma but aren't regular?
2
votes
0
answers
118
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 ...
- 121
0
votes
0
answers
49
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.
- 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 ...
- 329
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).
- 193
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 ...
- 367
7
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 ...
- 181
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 ...
- 383
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 ...
- 243
4
votes
1
answer
584
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 ...
- 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\} $$
...
5
votes
2
answers
205
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, ...
- 17k
0
votes
0
answers
141
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,...
- 1
1
vote
0
answers
42
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?
