yeah I'm sure that depends on how you construct your NFAs to begin with. outside of the confines of the usual regular grammars there's all kinds of stuff going on. I stuck to alternation and star with my toy engine
that was a long time ago I wonder where it is
well a+ is just aa* so it's not really needed
those are the two important ones
that and concatenation obviously
yeah sure. just order of operations if you take capture groups out of the equation
I think there's a Kleene algebra which basically takes the regex operations and makes a semiring
tl;dr math but with strings
addition is alternation, multiplication is concatenation and there's another operator that's closed for star
and no I didn't actually remember this I just remembered it existed and googled it
obviously these parts of CS were pretty thoroughly researched before we even had any friggin computers
likely due to the overlap with linguistics
oh yeah the connection of encoding things in numbers came from Godel
I'm sure making algebraic structures out of strings was not much of a stretch from that
kleene connected FSAs and regular languages first though
yeah it's called CS and the inevitable arms race to make as many computational models as possible before Turing comes in and says they're all the same everyone go home
lingustics is just a justification (and a place to start, cause strings and grammar)
@QPaysTaxes means it can do what a Turing Machine does, which is much nicer and simpler than hellish stuff like tag systems
not so much prove as philosophically state, see the church turing thesis
tl;dr computation is universal blah blah hey check out my new """industry""" standard
oh and something real abstract about humans being able to do it too and we're all just walking calculators haha
you can prove individually that a model is equivalent to a Turing Machine, but really we picked the Turing Machine for reasoning about computation just because people liked it
it's very close to stuff like push down automatas and the like and doesn't involve writing ten thousand parenthesis like in lambda calculus
it felt like a natural extension of other automatas I suppose
@QPaysTaxes I would rather just write Haskell
I would say that there is defintely a connection to any computer simply because of the sequential memory -- like a tape
@QPaysTaxes did that actually work
(sorry for slow typing I'm on a tablet)
Yeah it's priced like a textbook sadly but I wouldn't really consider it one
It dedicates about half a chapter to lambda calculus
It's mostly about complexity theory (so algorithms) but also hits up all the computational model stuff we talked about which is connected anyways
