UnderGround Forums
 

AcademicGround >> Language Question


4/15/04 3:09 AM
Ignore | Quote | Vote Down | Vote Up
jgibson
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 04/30/2001
Posts: 4029
 
Consider the language that the following grammar defines: (S) equals $ OR (W) OR $ AND (S) (W) equals abb OR a AND (W) AND bb Write all strings that are in this language that contain seven or fewer characters. I'm saying these are possible: $, abb, aabbbb, $$, $abb, $aabbbb
4/15/04 11:32 AM
Ignore | Quote | Vote Down | Vote Up
Andrew Yao
Send Private Message Add Comment To Profile

Edited: 15-Apr-04 11:29 AM
Member Since: 01/01/2001
Posts: 1742
Also $$$,$$$$,$$$$$,$$$$$$,$$$$$$$, $$abb, $$$abb, $$$$abb, aabb, $aabb, $$aabb, $$$aabb, . To do these kinds of problems, it's suicide to just try to randomly figure them out and hope you catch them all. I find it helps to do a diagram like this: And just try to do a normal tree traversal. Of course, it's not a true tree because it has cycles, so it is harder. There probably is an algorithm to find every path in a cyclical graph, but I don't know it.
4/15/04 1:02 PM
Ignore | Quote | Vote Down | Vote Up
hakujin
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 03/26/2002
Posts: 1418
*holds breath and runs away*
4/15/04 2:22 PM
Ignore | Quote | Vote Down | Vote Up
jgibson
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 04/30/2001
Posts: 4031
Andrew, Thanks for the diagram technique. It will certainly help in the future.
4/15/04 5:11 PM
Ignore | Quote | Vote Down | Vote Up
confusion
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 03/15/2002
Posts: 705
What class are you taking? Automata Theory?
4/15/04 6:12 PM
Ignore | Quote | Vote Down | Vote Up
jgibson
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 04/30/2001
Posts: 4032
Confusion, Data Structures
4/15/04 10:20 PM
Ignore | Quote | Vote Down | Vote Up
confusion
Send Private Message Add Comment To Profile

Edited: 15-Apr-04
Member Since: 03/15/2002
Posts: 706
Ah. My data structures course was just complexity theory, trees, stacks, queues, etc. All the fsm, turing machine, recursive languages were in automata theory. I aced both haha. Feel free to ask more questions, though I think Andrew has got the CS thing down better.

Reply Post

You must log in to post a reply. Click here to login.