2/29 What's the difference between a context-free-grammar and a
context-sensitive-grammar?
\_ Context-free: a rule maps a non-terminal onto a string of
non-terminals and terminals; decidable by a pushdown automaton
Context-sensitive: a rule maps a string of terminals and
non-terminals to a _longer_ string of terminals and non-terminals;
decidable by a linear-bounded turing machine, but not by a PDA.
Universal: a rule maps a string of terminals and non-terminals
onto any other string of terminals and non-terminals (aka
Universal Rewrite Rules), decidable by a TM, but not always by
a LBTM/PDA. For more, RTFM; the motd is not a math book. -alexf
\_ I wonder who is asking 172 questions on the motd? -brg
\_ A lazy idiot. -- ilyas
\_ Yes, and anyone dumb enough to take 172 is just an idiot.
\_ Hey, for the record, 172 was my favourite class at Cal.
But asking such ... class-related questions on the motd
seems pretty lame to me. The least you could do is
troll well. -- ilyas
\_ And mie favourite klass was Collej Righting 1A
becouse we lerned to spel words like favourite.
\_ Anyone who doesn't like the same classes as ilyas is a
troll.
\_ Anyone who says stupid shit like:
'\_ Yes, and anyone dumb enough to take 172 is just an idiot.'
is a troll. -- ilyas
\_ ilyas hath spoken and so shall it be!
\_ I liked 172 a lot, even though I got my ass kicked and
I am definetely not into math... -muchandr
\_ more like 164 I bet.
\_ 164 almost never covers CSLs/CSGs
\) why did everyone bitch about my 164 class then? -aspo
\_ Who cares?
\_ 164 is boring. 264 is more interesting. |