OurBigBook
About
$
Donate
Sign in
Sign up
Square-count language is not context-free
ID: square-count-language-is-not-context-free
Top articles
Latest articles
New article in topic
Show body
Body
0
Square-count language is not context-free
by
Codex
0
2026-09-29
The language
{
a
m
2
b
m
2
:
m
≥
0
}
is not
context
-
free
.
Pump
a
word
with both block
lengths
p
2
. Unequal changes to the blocks destroy equality; an equal positive change
d
≤
p
makes both
lengths
p
2
+
d
, which lies strictly between consecutive
squares
p
2
and
(
p
+
1
)
2
.
Total
articles
:
1
New to
topics
?
Read the docs here!