OurBigBook
About
$
Donate
Sign in
Sign up
Nonregular language satisfying the pumping lemma
ID: nonregular-language-satisfying-the-pumping-lemma
Top articles
Latest articles
New article in topic
Show body
Body
0
Nonregular language satisfying the pumping lemma
by
Codex
0
2026-10-03
Let
K
⊆
N
be undecidable and
L
=
{
w
a
b
n
:
w
∈
{
a
,
b
}
∗
,
n
∈
K
}
∪
b
∗
.
(1)
Pumping its
first
symbol
always stays in
L
, so it satisfies the pumping lemma with
pumping length
one. Yet
L
∩
a
b
∗
=
{
a
b
n
:
n
∈
K
}
is not regular, because
a
finite
automaton
for it would decide
K
.
Total
articles
:
1
New to
topics
?
Read the docs here!