2003 November 3rd, 09:41 PM
|
#1 (permalink) |
|
TestMagic Guru-in-Training
 Join Date: Oct 2003
Location: USA
Posts: 508
 |
Here we go again.
Q1) List in order of power (most powerful to least powerful): deterministic pushdown automaton (DPDA), deterministic finite automaton (DFA), deterministic 1-tape turing machine (TM), non-deterministic pushdown automaton (NPDA), nondeterministic finite automaton (NFA), non-deterministic 1-tape turning machine (NTM), deterministic 2-tape turing machine (NTM2), nondeterministic 2-stack pushdown automaton (NPDA2) Q2) Which of the machines listed above might be able to parse the language {ww : w is in {0,1}*} Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse" Q4) How about {0^n 1^n : n is a positive integer} Q5) How about {0^n 1^n 0^n : n is a positive integer} Q6) How about {01^n0 : n is a positive integer} Q7) For each language in Q3 thru Q6 that is context-free, give a context-free grammar. Q8) For each language in Q3 thru Q6 that is regular, give a regular expression. Q9) If a language is recognizable and co-recognizable, is it decidable? Q10) Categorize the following as decidable or not decidable: Checking if a string falls within a regular expression's language. Checking if a string falls within a context free grammar's language. Checking if a string falls within a turing machine's language. Checking if a regular expression generates all possible strings (e.g.: {0,1}*) Checking if a context free grammar generates all possible strings Checking if a recursive language contains all possible strings Q11) Are the following classes of languages closed under union, intersection, concatenation, Kleene closure, and complement? Regular languages Context free languages Recursive languages Recursively enumerable languages Q12) Give the best, average, and worst-case runtime for two stable comparison sorts. Q13) What is the run time of radix sort, if it relies on counting sort for the per-bit sorting, assuming that there are n elements, each containing k bits? Q14) What is the running time (in big-O notation) of the following function? Code:
function f(n) {
if (n <= 1) return 1;
return 3*f(n/2) + lg n;
}
Q16) What is the key invariant in quick sort? What is the key invariant in insertion sort? Q17) Define NP, NP-hard, and NP-complete. Q18) List the precondition(s) and the postcondition(s) implicit in the following function. Code:
function f(n, m) {
if (n < 0)
return n/m;
else
return m/n;
}
|
|
       
|
|
2003 November 3rd, 11:04 PM
|
#2 (permalink) |
|
I JUST got here.
Join Date: Oct 2003
Posts: 21
|
Q1) List in order of power (most powerful to least powerful): deterministic pushdown automaton (DPDA), deterministic finite automaton (DFA), deterministic 1-tape turing machine (TM), non-deterministic pushdown automaton (NPDA), nondeterministic finite automaton (NFA), non-deterministic 1-tape turning machine (NTM), deterministic 2-tape turing machine (NTM2), nondeterministic 2-stack pushdown automaton (NPDA2)
NTM = NTM2 = NPDA2, TM = TM2 = PDA2, NPDA, DPDA, DFA = NFA Q2) Which of the machines listed above might be able to parse the language {ww : w is in {0,1}*} TM Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse" PDA, S-> e | 1S1 | 0S0 Q4) How about {0^n 1^n : n is a positive integer} PDA, S-> 01 | 0S1 Q5) How about {0^n 1^n 0^n : n is a positive integer} TM Q6) How about {01^n0 : n is a positive integer} DFA, L=011*0 I think... please correct |
|
|
|
|
2003 November 4th, 04:03 AM
|
#4 (permalink) |
|
TestMagic Guru-in-Training
Join Date: Oct 2003
Location: Albania
Posts: 534
|
Q9) If a language is recognizable and co-recognizable, is it decidable?
If co-recognizable means that the complement of the language is recognizable, then it is decidable. A language is recursive (decidable)iff it and its complement are recursive enumerable (recognizable). Q10) Categorize the following as decidable or not decidable: Checking if a string falls within a regular expression's language. decidable Checking if a string falls within a context free grammar's language. decidable Checking if a string falls within a turing machine's language. not decidable Checking if a regular expression generates all possible strings (e.g.: {0,1}*) decidable (0*1*)* does for example Checking if a context free grammar generates all possible strings I think not decidable Checking if a recursive language contains all possible strings I think not decidable Q11) Are the following classes of languages closed under union, intersection, concatenation, Kleene closure, and complement? Regular languages Context free languages Recursive languages Recursively enumerable languages Regular Languages Closed under union concatenation Kleene closure intersection difference complement Context Free Languages Closed under Union Concatenation Kleen Star * Context Sensitive Languages Closed under Union Concatenation Kleen Star * Complementation Turing machine Languages Closed under union concatenation Kleene closure positive closure substitution intersection P viewed as a set of languages, is closed under union intersection concatenation complement Kleene star NP set is closed under union intersection concatenation Kleene star Q12) Give the best, average, and worst-case runtime for two stable comparison sorts. Q13) What is the run time of radix sort, if it relies on counting sort for the per-bit sorting, assuming that there are n elements, each containing k bits? Q14) What is the running time (in big-O notation) of the following function? function f(n) { if (n <= 1) return 1; return 3*f(n/2) + lg n; } log(n) Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort? Q16) What is the key invariant in quick sort? What is the key invariant in insertion sort? QS, all the elements on one side of the pivot are less than the elements on the other. IS, k is the current element, all elements 0 to k -1 are already sorted Q17) Define NP, NP-hard, and NP-complete. NP = non-deterministic polynomial, a language decidable by a NDTM, NP-hard an instance of NP NP-complete a set of NP-hard problems which can be reduced to one another in poly-time Q18) List the precondition(s) and the postcondition(s) implicit in the following function. function f(n, m) { if (n < 0) return n/m; else return m/n; } If we also want to require that f must return 10, what is the weakest precondition (in addition to the preconditions you listed above) that must be satisfied? Don't know what you mean by implicit, but here is a possible precondition all apples must be blue  .One possible precondition must be that m, n != 0 weakest precondition ((n < 0 AND n = 10m) OR (n > 0 AND m = 10n) ) |
|
|
|
|
2003 November 4th, 12:49 PM
|
#5 (permalink) |
|
TestMagic Guru-in-Training
Join Date: Oct 2003
Location: USA
Posts: 508
|
Here is an answer key, compiled from all your answers, and my own. (In some cases, your answers were so much better than anything I could come up with that I just plagiarized your work. Good job, guys!)
Items that could really use more discussion will be highlighted in orange. I will update this entry until no orange items remain. Q1) List in order of power (most powerful to least powerful): deterministic pushdown automaton (DPDA), deterministic finite automaton (DFA), deterministic 1-tape turing machine (TM), non-deterministic pushdown automaton (NPDA), nondeterministic finite automaton (NFA), non-deterministic 1-tape turning machine (NTM), deterministic 2-tape turing machine (NTM2), nondeterministic 2-stack pushdown automaton (NPDA2) NTM = NTM2 = NPDA2 = TM = TM2 = PDA2, NPDA, DPDA, DFA = NFA Q2) Which of the machines listed above might be able to parse the language {ww : w is in {0,1}*} TM Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse" PDA, S-> e | 1S1 | 0S0 (Thanks for the correction, Wood) Q4) How about {0^n 1^n : n is a positive integer} PDA, S-> 01 | 0S1 Q5) How about {0^n 1^n 0^n : n is a positive integer} TM Q6) How about {01^n0 : n is a positive integer} DFA, 011*0 Q7) For each language in Q3 thru Q6 that is context-free, give a context-free grammar. See above Q8) For each language in Q3 thru Q6 that is regular, give a regular expression. See above Q9) If a language is recognizable and co-recognizable, is it decidable? Decidable Q10) Categorize the following as decidable or not decidable: Checking if a string falls within a regular expression's language. Decidable Checking if a string falls within a context free grammar's language. Decidable Checking if a string falls within a turing machine's language. Not Decidable Checking if a regular expression generates all possible strings (e.g.: {0,1}*) Decidable Checking if a context free grammar generates all possible strings Not Decidable Checking if a recursive language contains all possible strings Not Decidable Q11) Are the following classes of languages closed under union (U), intersection (I), concatenation (C), Kleene closure (K), and complement (X)? Regular languages UICKX Context free languages UCK Recursive languages UICKX Recursively enumerable languages UIKX Context sensitive languages UKX Q12) Give the best, average, and worst-case runtime for two stable comparison sorts. Merge: O(nlgn), O(nlgn), O(nlgn), Insertion: O(n), O(nn), O(nn) Q13) What is the run time of radix sort, if it relies on counting sort for the per-bit sorting, assuming that there are n elements, each containing k bits? The counting sort uses O(n+d), where d is the number of digits, which is 2 here. O(n+2) => O(n) The radix sort uses k counting sorts, or O(kn) Q14) What is the running time (in big-O notation) of the following function? Code:
function f(n) {
if (n <= 1) return 1;
return 3*f(n/2) + lg n;
}
R(1) = 1 R(n>1) = 1+R(n/2) => R(n) = O(lg n) Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort? Insertion: O(n*n/8) Selection: O(n) Bubble: O(n*n/4) Q16) What is the key invariant in quick sort? What is the key invariant in insertion sort? QS, all the elements on one side of the pivot are less than the elements on the other, and after the nth iteration, all elements are in the right 1/2^n th fraction of the array. IS, k is the current element, all elements 0 to k -1 are already sorted Q17) Define NP, NP-hard, and NP-complete. NP = problems decidable in polynomial time on an NTM (or, equivalently, verifiable in polynomial time on a 1-tape TM) NP-hard = {languages L such that for all L’ in NP, L’ is reducible to L in polynomial time} NP-complete = NP intersect NP-hard Q18) List the precondition(s) and the postcondition(s) implicit in the following function. Code:
function f(n, m) {
if (n < 0)
return n/m;
else
return m/n;
}
Precondition: Either n < 0 and m <> 0, Or n <> 0 Postcondition: If n < 0, then f returns n/m If n >= 0, then f returns m/n (n < 0 & f=n/m) | (n >= 0 & f=m/n) If we want to force f to be 10, then we must require (n < 0 & n=10m) | (n > 0 & m=10n) |
|
|
|
|
2003 November 4th, 04:59 PM
|
#8 (permalink) |
|
TestMagic Guru-in-Training
Join Date: Oct 2003
Location: Albania
Posts: 534
|
Alba: my notes from Ullman say that CSL’s are not closed under star. Is that right?
Nonevent this is how I see it, if they a language is closed under concatenation why shouldn't it be closed under Kleen *, which after all is nothing more than multiple concatenations. here is a link where I saw it, http://www.cs.uiowa.edu/~hzhang/c135/weekb.pdf |
|
|
|
|
2003 November 4th, 05:06 PM
|
#9 (permalink) |
|
I JUST got here.
Join Date: Oct 2003
Posts: 21
|
Q11) Are the following classes of languages closed under union (U), intersection (I), concatenation (C), Kleene closure (K), and complement (X)?
Regular languages UICKX Context free languages UKXRecursive languages UICKX Recursively enumerable languages UIKX I remember context free languages are not closed under complement, thus not close under intersection. A intersect B = complement ((complement A) union (complement B)) |
|
|
|
Contact TestMagic TestMagic Forums Archive Privacy Statement
TestMagic Locations
Legal
Privacy
SEO by vBSEO 3.2.0
Copyright © 2009 TestMagic
Ad Management by RedTyger
Linear Mode
