Near Matches
Ignore Exact
Everything
2
Myhill Theorem proof that the balanced braces language is not regular (idea)
See all of Myhill Theorem proof that the balanced braces language is not regular
, no other writeups in this node.
(
idea
)
by
ariels
Sat Mar 11 2000 at 23:08:40
Consider the
word
s
w
1
= "
(
",
w
2
= "
((
",
...,
w
n
= "
(
"
n
,
...
(w
n
is n open braces). Then, using the notation of the
Myhill / Nerode theorem
, S(w
n
) is different for each n: it contains "
)
"
n
, but no other string of only close braces). Thus there are
infinite
ly many types for S(w), so by the
Myhill / Nerode Theorem
the
balanced braces language
is not a
regular language
.
balanced braces language
Myhill / Nerode Theorem
paren matching
Myhill Theorem proof that the "a^n b^n" language is not regular
Microsoft time
pumping lemma proof that the balanced braces language is not regular
regular language
Argument from Design
Transhumanist Terminology
I shall leave you
3816547290
Information War : Cryptography in World War II
properly matched string
Why won't people kick both parties out?
nested parentheses
Mathematical proofs: New York style
insta-raver
Gödel's theorem
information theory