driller for theory

nonevent99 · November 3, 2003

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 , 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?

function f(n) {
 if (n   return 3*f(n/2) + lg 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?

Q17) Define NP, NP-hard, and NP-complete.

Q18) List the precondition(s) and the postcondition(s) implicit in the following function.

function f(n, m) {
  if (n       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?

samlai · November 3, 2003

Q1) List in order of power (most powerful to least powerful): deterministic pushdown automaton (DPDA), deterministic finite automaton (DFA), deterministic 1-tape turing machine , 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

AlbaLed · November 3, 2003

Q1. More Powerfull = does something others cannot do (not does something faster)

NTM = NTM2 = NPDA2 = TM = TM2 = PDA2, NPDA, DPDA, DFA = NFA

Q6 correc!!!

Good job salmai

AlbaLed · November 4, 2003

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

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

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 :p.

One possible precondition must be that m, n != 0

weakest precondition

((n 0 AND m = 10n) )

nonevent99 · November 4, 2003

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 , 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 ©, 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?

function f(n) {
 if (n   return 3*f(n/2) + lg n;
}

R(n) = running time

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.

function f(n, m) {
  if (n       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?

Precondition:

Either n 0,

Or n 0

Postcondition:

If n

If n >= 0, then f returns m/n

(n = 0 & f=m/n)

If we want to force f to be 10, then we must require

(n 0 & m=10n)

wood · November 4, 2003

Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse"

NPDA, S-> e | 1S1 | 0S0

Why do you need a NPDA here? Wouldn't a PDA suffice?

AlbaLed · November 4, 2003

I agree wood, a PDA will suffice, ww% is a CFL

AlbaLed · November 4, 2003

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

samlai · November 4, 2003

Q11) Are the following classes of languages closed under union (U), intersection (I), concatenation ©, 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))

nonevent99 · November 4, 2003

That makes sense; I totally agree, so my notes must be in error. I'll change the orange above and close it out.

wood · November 4, 2003

Indeed. CFG intersect CFG does not necessarily lead to a CFG. However, CFG intersect regular language = CFG.

Wood

AlbaLed · November 4, 2003

What about CFL intersect Reg. Lang, and CFL intersect CFG?

AlbaLed · November 5, 2003

Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort?

According to Sedgewick (and I’m not sure I trust the answer for bubble)

Bubble: O(n*n/2)

Nonevent here is what I get for bubble, maybe you can trust me, forget Sedgewick :p

elements in bubble (smallest elem on top)

x

x1

probability of that x1 will bubble over x is 1/2

x

x1

x2

x3

probability of that x1 will bubble over x is 1/2, 
probability that x2 will bubble 1 spot  = 1/2, (if x2 probability that x2 will bubble 2 spots = 1/2, (if x2 probability that x3 will bubble 1 spot  = 1/2, (if x3 probability that x3 will bubble 2 spots = 1/2, (if x3 probability that x3 will bubble 3 spots = 1/2, (if x3 .............
Now we can see a trend develeping 
1/2 + 2/2 +3/2 + 4/2 ...................

if we do a summation we get sum(k=1 to n-1)[x/2] =

= 1/2 * sum(k=1 to n-1)(k)

= 1/2(n-1)(n-2) = O(n*n/4)

nonevent99 · November 5, 2003

Originally posted by AlbaLed

Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort?

According to Sedgewick (and I’m not sure I trust the answer for bubble)
Bubble: O(n*n/2)

Nonevent here is what I get for bubble, maybe you can trust me, forget Sedgewick :p

elements in bubble (smallest elem on top)
x
x1

probability of that x1 will bubble over x is 1/2

x
x1
x2
x3
probability of that x1 will bubble over x is 1/2, 
probability that x2 will bubble 1 spot  = 1/2, (if x2 probability that x2 will bubble 2 spots = 1/2, (if x2 probability that x3 will bubble 1 spot  = 1/2, (if x3 probability that x3 will bubble 2 spots = 1/2, (if x3 probability that x3 will bubble 3 spots = 1/2, (if x3 .............
Now we can see a trend develeping 
1/2 + 2/2 +3/2 + 4/2 ...................
if we do a summation we get sum(k=1 to n-1)[x/2] =
= 1/2 * sum(k=1 to n-1)(k)
= 1/2(n-1)(n-2) = O(n*n/2)

I do trust you, Alba, but that last line of your derivation confuses me. Doesn't the sum of (k=1 to n-1) equal (n-1)(n-2)/2?

Then S = sum(k=1 to n-1)[x/2]

= 1/2 * sum(k=1 to n-1)(k)

= 1/2(n-1)(n-2)/2 = n*n/4

Moreover, if I experimentally attempt to verify that the answer is n*n/4 using an applet such as

http://www.eca.com.ve/cs/it_page/Sort_Algorithms/bubble%20sort.htm

it invariably comes back as something very close to n*n/4 rather than n*n/2.

Finally, the usual bubble sort typically has n*(n-1)/2 =approx n*n/2 comparisons. I would expect that half of the comparisons would lead to swaps. That yields n*n/4.

These are the reasons I'm skeptical of Sedgewick. It just doesn't appeal to my gut. What's your take?

wood · November 5, 2003

That's true nonevent99. Looks like O(n*n/2) is a thigh upper bound for the worst case scenario. Your link shows that worst case (10 elements and 45 swaps). But in average, you'll get O(n*n/4) as you pointed out.

Wood

AlbaLed · November 5, 2003

I meant n*n/4 typo, checlk the time when I posted it, my eyes were ready to pop out into the keyboard at that time :D

nonevent99 · November 5, 2003

Oh, good. It makes sense that the average should be n*n/4 or so, and the worst case n*n/2 or so.

Thanks, guys. You are a big comfort.

CalmLogic · January 16, 2007

*** bump ***

ethanph · March 28, 2008

Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse"

PDA, S-> e | 1S1 | 0S0

(Thanks for the correction, Wood)

I check our notes in my class, WW% cannot be recognizable by any DPA. I think if we can figure out the CFL, it doesn't means it can be recognizable by DPA. NPDA can recognize some CFL that PDA cannot. Am I right?

driller for theory

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation