| |
| |
| |
|
Page: 1 2 3 4 5 6 7 8 9 10 11
Comments:
<0> augmented FSA may or may not advance in the string
<1> ah, so what's an augmented FSA?
<1> (and why would you ever want one?)
<0> an automaton where transitions are allowed to do stuff
<0> such as emit symbols
<1> ah, ok
<1> (I think I heard this called a tranducer)
<1> transducer)
<0> yes
<0> probably ;)
<0> or a rewrite-system or something like that
<0> yes
<2> So what do you mean by the total number of transitions up there?
<0> all the arrows in your FSA diagram
<2> Wouldn't that be one arrow per node?
<0> depth first search starts at the initial state, and proceeds by following the transitions
<0> no necessarily
<0> not*
<1> it seems to me that you could always force the string to advance one
<1> without loss of generality
<1> (that is, the set of possible transformations would be the same)
<1> (if you added this requirement)
<2> Well, I think in the kind of automaton I'm thinking of, it'd be one arrow per node.
<2> So would I be in an infinite loop after following N-1 arrows?
<0> if your FSA reads a string and advances 1 symbol at each state/transition, you're going to loop only as many times your string is long
<0> you just may end in an non-accepting state
<1> wasn't ihope_ suggesting a test for n-1 states without advancing the input string?
<2> There's no input here.
<1> output then :)
<1> oh, I see
<1> you could have an infinite output
<1> ihope_, are you familiar with the pumping lemma?
<0> therefore the need to detect cycles
<2> clausen: no.
<0> so it's verifiable by a modified depth-first search
<0> and colored nodes
<1> http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
<1> it's not exactly what you want, but the idea is the same
<1> (the basic idea is that if a string in a language is longer than the size of a FSA representing it, then the DFA must have cycled around, so you must be able to go around the cycle more or less times, and hence add or subtract substrings...)
<1> s/DFA/FSA/
<2> Um, there's no input string or anything; it's just a bunch of nodes with an arrow coming out of each node.
<1> ihope_, I know
<1> ihope_, but I think it's the same idea
<1> (as if there were an input string)
<1> in particular, I think your conjecture about n-1 states is about right
<1> (although I think it should be n states)
<1> and the logic is pretty much the same as the pumping lemma
<2> I think it's N-1.
<1> oh, I see
<1> you're right
<1> isn't it entirely deterministic
<1> in the sense that you go through a sequence of states
<1> and then arrive at the end?
<2> Well, there's no end, really.
<1> it seems like a trivial system
<1> there's no "end" state(s)?
<2> Right. You have to enter an infinite loop eventually.
<1> why wouldn't you just follow the FSA
<1> and look for the first time you are in the same state?
<1> (as you were at some point in the past)
<1> then that's your loop
<2> Well, if you had a number of states comparable to a googolplex, you can't really afford to put markers on states, can you?
<1> I guess not :)
<2> Running it for some time, making note of the state, running for some longer time, and comparing your new state to the old one uses less space but takes up more memory.
<2> Erm, takes more time, not more memory.
<2> Less space but more memory...
<1> I wonder if it's better to think of it as a permutation
<1> are you familiar with permutation groups?
<1> I think there's a bijection between your FSAs and a permutation
<2> What are they?
<1> notation: (123)(45)(6)
<1> would represent the function that maps 1 -> 2, 2 -> 3, 3 -> 1, 4 -> 5, 5 -> 4, etc.
<1> a permutation is a bijective self-map
<2> What if 1 goes to 2, 2 goes to 3, and 3 goes to 2?
<1> it turns out you can always represent a finite permutation in the notation above
<1> ihope_, no, 3 goes to 1
<1> note that (123) is the same as (231)
<1> (and 312)
<1> (and (312))
<2> So 3 can't go to 2?
<1> well, that would take 2 steps
<1> the permutation itself is just a function
<1> i.e. f(3) = 1
<1> f(1) = 2
<1> etc.
<1> f(f(3)) = 2 :)
<2> f(f(f(x))) = x?
<1> notice that f is a lot like your FSA transition function
<1> ihope_, if x is 1, 2 or 3
<1> but f(f(f(4))) = 5 in the above example
<2> Oh... so it's f(f(f(f(f(f(x)))))) = x?
<1> yes
<2> Or f^6(x), if you like readability :-)
<2> Now let's see here...
<2> > map (foldl' lcm 1 . enumFromTo 1) [1..10]
<1> that's a consequence of Lagrange's theorem
<3> [1,2,6,12,60,60,420,840,2520,2520]
<1> (are you familiar with group theory?)
<4> Yes
<4> oh... =)
<2> No.
<1> (you should learn it some day. it's lots of fun :)
<4> clausen: Isn't Lagrange's Theorem that if H<G, the |G|=|H|*[G|H]?
<4> Or [H|G], whichever is the index of H in G.
<2> So that up there is A003418...
<1> |Steve|, yes
<1> I might need to retract my earlier statement :)
<1> (I'm wondering if I can think of it as a group action...)
<4> Okay, time to go teach discrete math.
<1> have fun :)
<2> I like discrete math. Real numbers are icky.
<1> ihope_, what about topology?
<1> that's not icky :)
<1> (or metric spaces)
<4> Thanks.
<2> Tell me when topology can be expressed nicely with algebraic datatypes :-P
<4> ihope_: Sets.
<2> Sets?
<1> ihope_, don't you think the concepts of "interior", "boundary", etc. from topology are cool enough on their own?
<2> Well, discrete math is nice and simple...
<1> have you ever studied topology?
<4> Except when you have to solve diophantine equations. =)
<1> discrete math can easily get into combinatorial nightmares
<4> (Okay, I lied, breakfast then teaching.)
<4> I'll be teaching that "p if q" means "p => q."
<2> Um... "if p then q"?
<4> Hopefully not combinatorial nightmares this cl***.
<4> er,
<4> q => p
<4> heh
<4> I thought one thing and wrote another.
<1> I'd better go
<1> anywy, ihope_, I really recommend you take a look at topology
<2> Okay, I will.
<1> if you like abstract data types, I think there's a good chance you'll like topology too
<2> Bye.
<1> bye :)
<4> Group theory is more interesting.
<4> Heh. Nothing like some porn and cash.
<2> Wait... I didn't say abstract datatypes, did I?
<4> No.
<4> You said algebraic.
<4> Which is why you should study...algebra.
<5> I thought you're teaching, Steve :P
<4> heh
<4> soon
<4> Still eating breakfast.
<5> :P
<4> I realized the bus doesn't come for another half hour.
<4> So I've got time to get into a math frame of mind.
Return to
#math
or
Go to some related
logs:
linux-gate etch
pcntl_fork daemon
XMLHttpRequest setRequestHeader Set-Cookie Cookie
do mongoose like to kill cobras
pipe prozy
#linux
#bash
#math
dooberi config
#gimp
|
|