nonevent99 Posted November 5, 2003 Share Posted November 5, 2003 Q1) What machine recognizes regular languages? What machine recognizes context free languages? What machine recognizes recursively enumerable languages? Is there a strict hierarchy, and if so, what is it? Q2) If X is a CFL and Y is regular, is X intersect Y regular? How about CFL? How about recursively enumerable? Q3) How do "recursively enumerable" and "recursive" differ? Q4) What does "reducibility" mean? Who cares (in the context of recursiveness, and also NP-completeness)? Q5) What is the Church-Turing thesis, and who cares? Q6) Give an example of a CFG that is ambiguous. Q7) Give an example of a set for which no CFG exists. Q8) Give an example of a left-associative grammar. Q9) What are LL and LR grammars, and who cares? Q10) What is "tape"? Does adding more "tape" to a Turing Machine increase its power? Why or why not? (This is an intentionally ambiguous question. Take it where you will.) Q11) What is "stack"? Does adding more "stack" to a CFG-recognizing machine increase its power? Why or why not? (Ditto) Q12) Give best, average, and worst case big-O bounds on the runtime of your favorite sort. Why is it your favorite? How do you know that these are the correct big-O bounds? Q13) Give an example of your favorite greedy algorithm and explain why it's so greedy and why it's your favorite. Q14) Give an example of your favorite dynamic programming algorithm and explain why it's so dynamic and why it's your favorite. Q15) Define "Invariant", "Precondition", and "Postcondition" (added by wood) Q16) If L is recursive, then, mark T or F for each one of the statements below: ( ) L is recursively enumerable ( ) L is decidable ( ) L is infinite ( ) L' is recursive ( ) L' is recursively enumerable ( ) L' is decidable ( ) L' is infinite ( ) Could L represent all the prime numbers? Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Q1) What machine recognizes regular languages? What machine recognizes context free languages? What machine recognizes recursively enumerable languages? Is there a strict hierarchy, and if so, what is it? DFA, NDFA - regular languages PDA, NPDA - CFL TM - recursively enumerable languages I had found a nice figure showing the strict hierarchy with niice bubbles and stuff. Let me see if I can find it again. Q2) If X is a CFL and Y is regular, is X intersect Y regular? How about CFL? How about recursively enumerable? X intersect Y is CFL. CFL intersect CFL or recursively enumerable is not necessarily CFL. Q3) How do "recursively enumerable" and "recursive" differ? There's a TM for recursive languages that given a sentence, it either accepts it or rejects it. For recursively enumerable, a TM might never accept or reject, and therefore never halt. Q4) What does "reducibility" mean? Who cares (in the context of recursiveness, and also NP-completeness)? Reducibility is the process of "rephrasing" a problem as another problem in order to figure out if it is as harder as the other problem. In case of NP-completeness, if any language L' in NP can be reduced to a language L then, the problem is NP-hard. If L is also NP, then L is NP-complete. Q5) What is the Church-Turing thesis, and who cares? Church thesis is the premise that recursive functions and TMs are capable of representing every function that is computable of partially computable. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 context-sensitive language intersect CFL = ?????????? Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Not sure what you mean... never seen it. You're asking what's the intersection between a CFL language and all the languages represented by a CFG??? Does that make sense? Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 you were right wood did not make much sense. I meant context sensitive intersect context free language ??? Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Dunno then. I would guess CSL though. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 I dunno either, but I think CSL, similar to CFL intersect regular. I'll dig the net for this, and let you know if I find something Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Q6) Give an example of a CFG that is ambiguous. S -> A A -> A+A|A * A A -> a|b|c Try deriving the following in two different ways a+b*c Q7) Give an example of a set for which no CFG exists. {ww | w a word over {C,G, E, R, S}*} example CSGRECSGRE Q8) Give an example of a left-associative grammar. A -> Aa | Bb B -> Cc |Aa C -> Bc |Bb Quote Link to comment Share on other sites More sharing options...
basantikaveeru Posted November 6, 2003 Share Posted November 6, 2003 Q1) What machine recognizes regular languages? What machine recognizes context free languages? What machine recognizes recursively enumerable languages? Is there a strict hierarchy, and if so, what is it? RE - DFA/NDFA CFL - PDA REL - Turing machine RE Q2) If X is a CFL and Y is regular, is X intersect Y regular? How about CFL? How about recursively enumerable? CFL intersect RE = CFL Q3) How do "recursively enumerable" and "recursive" differ? RE Recursive langugaes can be generated and recognized by an algorithm. REL can also be generated by an algorithm, but may not be recognizable by one i.e. algo can run forever while trying to recognize one. Q4) What does "reducibility" mean? Who cares (in the context of recursiveness, and also NP-completeness)? One NP complete problem can be "reduced" to another one, by a ploynomial time algo. Recursiveness?? Q5) What is the Church-Turing thesis, and who cares? All computable functions can be computed on Turing machine. Q7) Give an example of a set for which no CFG exists. a^nb^nc^n where n>0 Q8) Give an example of a left-associative grammar. S->E+T T->E+T|E Q9) What are LL and LR grammars, and who cares? LL - left to right scan, leftmost reduction LR - left to right scan, rightmost reduction (corrected by wood) Q10) What is "tape"? Does adding more "tape" to a Turing Machine increase its power? Why or why not? (This is an intentionally ambiguous question. Take it where you will.) Not sure, I guess more tape more power. Q11) What is "stack"? Does adding more "stack" to a CFG-recognizing machine increase its power? Why or why not? (Ditto) adds more power, can become CFG recognizing m/c to TM Q16) If L is recursive, then, mark T or F for each one of the statements below: (T) L is recursively enumerable (T) L is decidable (T) L is infinite (T) L' is recursive ( T) L' is recursively enumerable ( T) L' is decidable ( T) L' is infinite (T) Could L represent all the prime numbers? Quote Link to comment Share on other sites More sharing options...
Laks Posted November 6, 2003 Share Posted November 6, 2003 Q9) What are LL and LR grammars, and who cares? LL grammars are CFG, that are not ambiguous and not Left recursive.... They are used by predictive parsers...{LL(1) grammars are used here} The first L stands for "we scan the input from left to right" Second L for "we produce the leftmost derivation" the number in the bracket (1) stands for the number of look ahead symbols for the parsing action. An LR is also a CFG...."L" -> scan the input from left to right" and R-> "we construct a rightmost derivation"... An LR grammar is way more powerful than a LL grammar. They are also used majorly for parsing. LR parsers can be constructed for virutally every programming construct for which a CFG can be written. Various LR grammars used actively for parsing are CLR (cannonical LR) and LALR (look-ahead LR). The famous YACC - Yet Another Compiler Compiler uses LALR(1) Cheers' Laks Quote Link to comment Share on other sites More sharing options...
rafi_dery Posted November 6, 2003 Share Posted November 6, 2003 Laks: Do LR parsers also have limitations? (ambiguity? associativity?) Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by wood Q1) What machine recognizes regular languages? What machine recognizes context free languages? What machine recognizes recursively enumerable languages? Is there a strict hierarchy, and if so, what is it? DFA, NDFA - regular languages PDA, NPDA - CFL PDA's cannot decide all CFLs, only the LR subset, right? TM - recursively enumerable languages I had found a nice figure showing the strict hierarchy with niice bubbles and stuff. Let me see if I can find it again. Q2) If X is a CFL and Y is regular, is X intersect Y regular? How about CFL? How about recursively enumerable? X intersect Y is CFL. CFL intersect CFL or recursively enumerable is not necessarily CFL. right Q3) How do "recursively enumerable" and "recursive" differ? There's a TM for recursive languages that given a sentence, it either accepts it or rejects it. For recursively enumerable, a TM might never accept or reject, and therefore never halt. right Q4) What does "reducibility" mean? Who cares (in the context of recursiveness, and also NP-completeness)? Reducibility is the process of "rephrasing" a problem as another problem in order to figure out if it is as harder as the other problem. In case of NP-completeness, if any language L' in NP can be reduced to a language L then, the problem is NP-hard. If L is also NP, then L is NP-complete. right Q5) What is the Church-Turing thesis, and who cares? Church thesis is the premise that recursive functions and TMs are capable of representing every function that is computable of partially computable. right. It is an assurance to us that the computers of today are capable of doing anything a computer will ever be capable of doing. (In that academic sense that doesn't really matter to real engineers.) Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by AlbaLed Q6) Give an example of a CFG that is ambiguous. S -> A A -> A+A|A * A A -> a|b|c Try deriving the following in two different ways a+b*c good! Q7) Give an example of a set for which no CFG exists. {ww | w a word over {C,G, E, R, S}*} example CSGRECSGRE good! Q8) Give an example of a left-associative grammar. A -> Aa | Bb B -> Cc |Aa C -> Bc |Bb good! What's the general principle you are demonstrating here. Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by basantikaveeru Q7) Give an example of a set for which no CFG exists. a^nb^nc^n where n>0 Another really nice example! Q9) What are LL and LR grammars, and who cares? LL - left to right scan, leftmost reduction LR - left to right scan, rightmost reduction (corrected by wood) Do all LR parsers generate rightmost reductions in reverse? Q10) What is "tape"? Does adding more "tape" to a Turing Machine increase its power? Why or why not? (This is an intentionally ambiguous question. Take it where you will.) Not sure, I guess more tape more power. Adding a second tape does not add power. However, allowing the TM to use an infinite linear tape (vs only a short little snippet of tape memory) does indeed add power. TMs with only finite tape can only decide CSLs. TMs with infinite tape can recognize all recursively enumerable languages. Q11) What is "stack"? Does adding more "stack" to a CFG-recognizing machine increase its power? Why or why not? (Ditto) adds more power, can become CFG recognizing m/c to TM Right! A two-stack NPDA can recognize all recursively enumerable languages, so adding a stack adds power. Obviously, allowing an infinite stack vs finite stack also adds power. Q16) If L is recursive, then, mark T or F for each one of the statements below: (T) L is recursively enumerable (T) L is decidable (T) L is infinite NOT decidable languages are infinite. Consider {0}. However, the converse is true. All finite languages are decidable (with a DFA). (T) L' is recursive ( T) L' is recursively enumerable ( T) L' is decidable ( T) L' is infinite Nope. Same reason as above. (T) Could L represent all the prime numbers? If you're asking whether the set of prime numbers is decidable, the answer is yeah, just try dividing by all smaller integers. Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Q1) What machine recognizes regular languages? What machine recognizes context free languages? What machine recognizes recursively enumerable languages? Is there a strict hierarchy, and if so, what is it? [blue]DFA, NDFA - regular languages PDA, NPDA - CFL PDA's cannot decide all CFLs, only the LR subset, right? Yes, you're right. There are CFLs that can't be recognized by a PDA, they need a NPDA. Example is { wwT | ... } See: http://cs.wwc.edu/~aabyan/Theory/automata_def.html#PDA Quote Link to comment Share on other sites More sharing options...
samlai Posted November 6, 2003 Share Posted November 6, 2003 context-sensitive language intersect CFL = ?????????? A context-sensitive language is closed under complement and union, so it is closed under intersection (A intersect B = (A' union B')'). A context-free language is a context-sensitive language, but not the other way around. So, context-sensitive language intersect context-free language is context-sensitive. That may not be the tighest bound, but it is all I can come up. Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by samlai context-sensitive language intersect CFL = ?????????? A context-sensitive language is closed under complement and union, so it is closed under intersection (A intersect B = (A' union B')'). A context-free language is a context-sensitive language, but not the other way around. So, context-sensitive language intersect context-free language is context-sensitive. That may not be the tighest bound, but it is all I can come up. Good job!!!!!!! I wouldn't have gotten that one. Let's see, a CFL is a CSL, and CSL's are closed under intersection, so CFL intersect CSL is a CSL. For sure, CSL intersect CFL isn't a CFL. For example, if L is absolutely definitely a CSL but not a CFL, and M = {0,1}* (ie, the entire universe), then L intersect M is L. Which isn't a CFL. So CSL intersect CFL is not a CFL, necessarily. More generally, Samlai has demonstrated a very useful technique, which also applies to the CFL intersect regular problem. If you have one class of languages C1 that is closed under intersection, and another class of languages C2 is a strict subset of C1, then a similar theorem exists: If L is in C1 and M is in C2, then L intersect M is in C1 but not necessarily in C2. This could be applied, for instance, to C1 = recursively enumerables and C2 = recursives. This means that a recursive language intersect a recursively enumerable language is definitely recursively enumerable but not necessarily recursive. Thanks again, Samlai!!!! Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 nonevent I think in the last paragraph you interchanged recursive recursive enumerable. Recusive languages are a strict subset of recursive enumerables, not the other way around. Good job Salmai and nonevent Quote Link to comment Share on other sites More sharing options...
rafi_dery Posted November 6, 2003 Share Posted November 6, 2003 nonevent, you probably meant R.E intersect R is R.E but not necessarily R, right? Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by AlbaLed nonevent I think in the last paragraph you interchanged recursive recursive enumerable. Recusive languages are a strict subset of recursive enumerables, not the other way around. Good job Salmai and nonevent Doh! :yuck: Thanks, Alba and Rafi. I'm glad you get the gist, though. Quote Link to comment Share on other sites More sharing options...
samlai Posted November 6, 2003 Share Posted November 6, 2003 :o Thanks, the idea just came to me. Just call me Sam. Lai is my last name. You guys are really good at the hardware stuff. I am very impressed. Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by samlai :o Thanks, the idea just came to me. Just call me Sam. Lai is my last name. You guys are really good at the hardware stuff. I am very impressed. Ok, Sam! You have a very good intution for the theory stuff! Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Q12) Give best, average, and worst case big-O bounds on the runtime of your favorite sort. Selection sort, O(n^2) all the cases Why is it your favorite? Because it is slow How do you know that these are the correct big-O bounds? I saw them in wood's thread:D:D:D:D:D Q15) Define "Invariant", "Precondition", and "Postcondition" Invariant -> as in loop invariant for example, is a condition that does not change regardless of execution path/times. Precondition -> a condition that has to hold before the execution of some statement(s) to guarantee the postcondition Postcondition -> a condition that holds after execution of some statement(s) ususally this is what we want BONUS Weakest Precondition -> least restrictive precondition that guarantees the postcondition. Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Hey, this is plagiarism!! :D :D Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Q12) Give best, average, and worst case big-O bounds on the runtime of your favorite sort. Selection sort, O(n^2) all the cases Why is it your favorite? Because it is slow How do you know that these are the correct big-O bounds? I saw them in wood's thread:D:D:D:D:D [green]I wish I could go through a teleporter Star Trek-wise immediatley after Wood and have Scotty imprint everything Wood ever wrote into my brain! :o My favorite sort is probably radix. When I learned of it, several years ago, my immediate response was, "Ok, we have an O(n) sort and don't have to worry about that problem any more." I thought it was a silver bullet.Since then, of course, I've learned about its limitations: it generally relies on counting sort, which requires extra swap space, and it doesn't work at all on floating point numbers. But at the time I thought it was the be-all-and-end-all of sorts because it has a runtime of O(n) in best, average, and worst cases. I know they are the correct bounds because I, too, have seen Wood's post. ;) Q15) Define "Invariant", "Precondition", and "Postcondition" Invariant -> as in loop invariant for example, is a condition that does not change regardless of execution path/times. Precondition -> a condition that has to hold before the execution of some statement(s) to guarantee the postcondition Postcondition -> a condition that holds after execution of some statement(s) ususally this is what we want BONUS Weakest Precondition -> least restrictive precondition that guarantees the postcondition. Nice, Alba! Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.