Our teachers, in their infinite wisdom, have decided that we shall not have help for our homework (which comprises 50% of our grade) after 6:30 the day before it is due. So I need yer help... *blush*
Ok, here are the questions and the answers I've attempted to make so far. I'm pretty sure they are wrong... correct answers and an explanation of how in the hell you get them would be much appreciated. Because I really have no idea... *sigh*
1) In each case, say what language is generated by the context-free grammar with the indicated productions.
e) S -> aS | bS | a
My Answer: (a*+b*)*a
f) S -> SS | bS | a
My Answer: (b*a*b*)^2 + b*a
2) Find the CFG's generating these languages:
b) {(a^i)(b^j)(c^k) | j = i + k}
My Answer: Bleh, just noticed I was trying to solve the wrong one. Will try this one... but probably can't do it either...
c) {(a^i)(b^j)(c^k) | i != j + k}
f) {(a^i)(b^j)(c^k) | i = j or i = k}
i) {(a^i)(b^j) | i < 2j }
3) In each case, show the grammar is ambiguous and find an equivalent unambigious grammar:
a) S -> SS | a | b
d) S -> aSb | aaSb | lambda
Ok... now I just gotta hope someone is on who is willing and able to answer these... heh. Of to beat my head against the wall some more in the meantime.
Sarvis
Help! (With CS Theory homework...)
Heh. I know the feeling Gind... but I'll be lucky to get a C at this rate. I don't have an irc client here either so that option's pretty much out. Just figured with all the good coders hanging around here I might stand a good chance.
Yayaril - Yep. Would have if that section existed... I really don't have many options right now since I can't obtain help anywhere else. Thanks to the teachers deciding it was more important to have us fail to do things on their timeschedule than for us to actually learn the material.
Sarvis
Yayaril - Yep. Would have if that section existed... I really don't have many options right now since I can't obtain help anywhere else. Thanks to the teachers deciding it was more important to have us fail to do things on their timeschedule than for us to actually learn the material.
Sarvis
1.e your answer seems correct to me, but can be simplified.
1.f consider S->SS->SSSS->SSSSSSSS->bSbSbSbSbSbSbSbS->babababababababa, which I dont think you're answer handles, and unless I've totally forgotten the notation abab fits your answer but cannot be generated by the given cfg. cfg's strings can start with a|b, but must end in a
1.f consider S->SS->SSSS->SSSSSSSS->bSbSbSbSbSbSbSbS->babababababababa, which I dont think you're answer handles, and unless I've totally forgotten the notation abab fits your answer but cannot be generated by the given cfg. cfg's strings can start with a|b, but must end in a
Nope, didn't ever have to learn context free grammer 
I did have to learn the basics of Turing Machines, but that was for my classes on AI and Algebraic Structures.
Don't wish too quickly, we call it the "Colorado School of Masochism" for a reason
(Besides, I am writing this from a Nonlinear Circuit Analysis lab and I'm a Math/CS Major!)
I did have to learn the basics of Turing Machines, but that was for my classes on AI and Algebraic Structures.
Don't wish too quickly, we call it the "Colorado School of Masochism" for a reason
(Besides, I am writing this from a Nonlinear Circuit Analysis lab and I'm a Math/CS Major!)
if you want others i do dem tonight. Email me at magnich@stanford.edu
Heh... I actually managed to explain an integral to my roommate last night. It took me half an hour, and most of my existing brainpower... but I got it right!
On a side note, it's interesting to note that while our professors consider this an important course for us to have, none of the professional programmers around sojourn could answer any of those questions.
On a side note, it's interesting to note that while our professors consider this an important course for us to have, none of the professional programmers around sojourn could answer any of those questions.
Sarvis:
Professors consider a great many things important that have absolutely no real world application, particularly for programmers.
On the other hand, they also do not emphasisize some things nearly enough.
CFG is only important if you are working in a field which uses it. Which anymore finding one is getting increasingly difficult.
*Please* though, for my sake and the sake of the programmers you will work with in the future, do the following:
1) Learn UML
2) Become at least vaguely familiar with asymptotic notation.
------------------
Elseenas of No House Worth Mentioning
Professors consider a great many things important that have absolutely no real world application, particularly for programmers.
On the other hand, they also do not emphasisize some things nearly enough.
CFG is only important if you are working in a field which uses it. Which anymore finding one is getting increasingly difficult.
*Please* though, for my sake and the sake of the programmers you will work with in the future, do the following:
1) Learn UML
2) Become at least vaguely familiar with asymptotic notation.
------------------
Elseenas of No House Worth Mentioning
UML: They are teaching UML in the beginning programming classes these days at my school. However I started a bit before that started, so don't know it yet... heh. Been meaning to learn it on my own, but not nearly enough time during the quarter... and no motivation during break.
Asymptotic Notation: err...? What?
Asymptotic Notation: err...? What?
Return to “S3 General Discussion Archive”
Who is online
Users browsing this forum: No registered users and 31 guests