Near Matches
Ignore Exact
Full Text
Everything
2
Myhill Theorem proof that the balanced braces language is not regular
(
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
.
printable version
chaos
Myhill / Nerode Theorem
balanced braces language
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
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
Godel's theorem
information theory
Y'know, if you
log in
, you can write something here, or contact authors directly on the site.
Create a New User
if you don't already have an account.
Epicenter
Login
Password
remember me
password reminder
register
Everything2 Help
Cool Staff Picks
Drink up!
Dorian
The Beatles
Pilots' Jargon
Hyperion
fire breathing
Going to the movies in Thailand
Seasonal Affective Disorder
algebra
Crimean War
surrealism
Choosing a node title
I will be the first thing you will be thinking about after you wake
conference call etiquette
New Writeups
omegle
(
thing
)
by
Glowing Fish
explosively formed penetrator
(
thing
)
by
Yurei
How the Terrorists Won the War
(
idea
)
by
Yurei
Welcome to Soviet America
(
idea
)
by
Wetfire
Anambe
(
person
)
by
Texwiller
The Remains of the Day
(
review
)
by
Oolong
December 10, 2009
(
person
)
by
clifftrapremover
lifetime guarantee
(
idea
)
by
Tem42
The Barefoot Contessa
(
person
)
by
NanceMuse
How the Terrorists Won the War
(
idea
)
by
mullakamakalaka
Bastard!!
(
review
)
by
Hazelnut
FUGM
(
thing
)
by
artman2003
Persipan
(
thing
)
by
alex
Amanaye
(
person
)
by
Texwiller
Your heartbreak may vary
(
fiction
)
by
Intentions
(
more
)