| Recent Posts | About the Author | Navigation |
|---|---|---|
|
|
David is an occasional blogger, software engineer, Nintendo fanboy, liberal, news magazine addict, voracious TiVo user, and bibliophile. He was born in St. Louis, grew up in southern Indiana, and returned to St. Louis to attend Washington University. He hasn't managed to escape yet. He's a fan of free wine tastings, too many tv shows to name, and eating out. David makes his living developing web applications used internally by his employer. He doesn't blog about work because he's heard too many stories about that causing workplace troubles. There's more on the about page. |
|
| Recent Comments | ||
|
|
||
| Recent Photos | ||
|
|
||
30 January 2002 - 10:34 pm
My friend Chris is signed on as WUcs431, thinking he can make some easy money by answering cs431 student's question over AIM (a system implemented by the 431 professor). I am FuSoYu, pretending to be the stupidest kid in the class. 431 is the class Chris and I TA, and it covers finite state machines and compilers. Our conversation follows. (Chris remained rather level-headed in the face of amazingly stupid questions, don't you think?)
FuSoYu (10:09:59 PM): how do I do lamda elimination?
FuSoYu (10:14:41 PM): actually, what is lamda?
WUcs431 (10:15:49 PM): lambda is when you can go from one state in a finite state machine to another without consuming any symbol or taking any action
FuSoYu (10:16:01 PM): cool
FuSoYu (10:16:02 PM): thanks
WUcs431 (10:16:11 PM): sure
FuSoYu (10:16:15 PM): why would you want to eliminate that?
WUcs431 (10:17:34 PM): because when you're designing a finite state machine, you want your states to have a purpose. It's easier to map out and understand that on an 'a' you go to state 2 and on a 'b' you go to state 3 than if there was a chance you could be in any number of states.
WUcs431 (10:17:54 PM): a lambda leads to uncertainty about where you are
FuSoYu (10:18:17 PM): so lambda is bad.
WUcs431 (10:18:46 PM): in essence, yes
FuSoYu (10:20:10 PM): can i just replace lambdas with something else?
WUcs431 (10:20:55 PM): not accurately, you have to go through and make the chart that Dr. Cytron talked about in class in order to make sure that the machine you make accepts the same language as the one with lambdas
FuSoYu (10:21:48 PM): can i use finite state machines to translate from a language with lambdas to one without?
WUcs431 (10:23:14 PM): you don't want to use a machine, you want to make a machine. First you have a language that uses lambdas. You can show this language as a finite state machine (FSM). Then you go through the process to eliminate lambdas to get a new FSM, and you can translate this FSM back into a corresponding language that is identical in syntax but without lambdas
FuSoYu (10:23:34 PM): okay that makes sense
FuSoYu (10:23:35 PM): thanks
WUcs431 (10:23:39 PM): sure
Posted by on 30 January 2002 at 10:34 PM
Comments