12/10/11: ======================================================= Mapping reductions and "if and only if". When you do a mapping reduction of A to B, written A <=m B, you do this: * You show that x in A IF AND ONLY IF f(x) in B this is where IF AND ONLY IF appears * Then you can ask "what does this have to do with decidability" All you've shown is : If B is decidable, A is decidable. Why and how? When you assume B has a decider, say D_B, one can obtain a decider for A as follows (call it D_A): D_A(x) { if D_B(f(x)) accepts, then accept else reject } 12/09/11: ======================================================= Some clarifications on Asg11 1. The proof structure is similar to that worked out in class for A_TM 2. Here, we build two copies of A_TM because one can definitely tell when M accepts w and the other can tell when definitely M rejects w (because the second copy gets M with accept and reject states swapped) 3. You just need to state what such a proof would mean. i.e Say some proved for you that A_TM <=m PCP. Then what is the "if and only if" statement you would be making at that point? It's a 5% question so only this much is being asked 4. English is ambiguous. Try to use the variables I mentioned. The BDD may "boil away" some variables (not show them). That is because those variables don't affect the proof. So that's fine. BDDs are known to drop redundant variables automatically. 12/08/11 and 12/07/11: ======================================================= > Do you want us to name our assignment 11 write-ups something specific? > asg11.pdf or asg11.txt will do (or asg11-q1.pdf asg11-q2.txt ... i.e. separate files ) ======================================================= > What does this from the homework mean: > > ATM ≤m PCP It means atm --mapping reduction --> pcp (explained in one of my notes). Why use this notation? It means A_TM less hard or same hardness as PCP (This is standard notation and a useful read.) [ also in faq ] ======================================================= > Where's DDcal ? See /home/cs3100/DDcal (binary) and /home/cs3100/DDcalExs (examples + documentation) This is in lab3-20.eng.utah.edu for instance. Other machines may also find this. If you used ~cs3100/DDcal for the executable and "cd ~cs3100/DDcalExs" to visit the examples directory, you should be fine. Let me know if not. 12/06/11: ======================================================= * No office hours held next week (me or TAs). The TAs have exams, and I have a trip coming up. Questions still welcomed via email * Sample final exam to be posted today; will be gone over on Thu * Today's lecture (12/6) is on BDDs; notes online * Real final exam 12/16 1030am in our class. I'll assign enough questions to fill 100 minutes (out of 2 hours). Then I'll give you some extra-credit questions for the remaining 20 mins. The points of those extra-credit questions will be added into your midterm scores according to some formula (TBD), to help you make up some of the lost points * To show that your project is working, you may provide more info than those 6 pages. For instance, you can submit screen-shots or otherwise capture your machine's working. You can submit it in a tarball called ExtraMaterial.tar.gz or ExtraMaterial.zip 12/05/11: ======================================================= The project report length was clarified to be 6 pages single spaced. I don't go by length - rather, by content and quality. I should have said that for reports with N members, each member had to write something explaining their work... and we have up to 4 members in some cases. Thus, to be fair, for N=3, 2, and 1, I'll expect proportionately shorter reports. 12/04/11: ======================================================= Reminder: Project reports due Dec 11th (see Asg10 where the project website info was requested). The 6-page report is single-spaced (see L20 where the project report requirements are described). 12/03/11: ======================================================= There is more than one way to write an algorithm. Just because a language is infinite and your attempt to enumerate it will loop DOES NOT mean that there can't be another algorithm that avoids such enumeration. E.g. to check if a DFA accepts any odd string at all, it is not smart to just enumerate all strings accepted by the DFA. Why can't one build another DFA that has a certain language (e.g. all strings over Sigma of odd length). Then you can do some Boolean operation between the DFA? (e.g. union, intersection, etc.)? 12/02/11: ======================================================= > I understand that for finding the cardinality of Acfg will require two > separate similar maps but I'm not sure how I should go about mapping > this language. The problem is simple : 1) Find a way to send each Nat into a distinct G,w pair. All Nat must be mapped from, but you don't need to hit all G,w pairs. Hint: You are allowed to choose either a fixed G and merely vary w, or fix w and vary G. 2) Find a way to send each G,w pair into a distinct Nat. All G,w pairs need to be mapped from, but you don't neet to hit every Nat. Hint: G and w are, after all, strings. 12/01/11: ======================================================= > I do not understand what question 3 is asking on the homework. It > asks for use to use SB to present a way to count the RE over {a,b} and > then present the answer as a cardinal number. I really do not > understand at all what this is asking for, since SB seems to only > apply to two distinct data sets and proving a bijection exists. Yes > So is the question talking about regular expressions as strings (such as > a*b, a+b, aa+bb) and the other data set is {a,b}*? Not quite. The wording is precise but understanding what it says isn't that easy (deliberately kept so, as you learn by trying to decipher such incantations), so let me break it down. When asked to "measure" the cardinality of the set of regular expressions, or any set S for that matter, you have only a few "measuring jars" at your disposal: 1) either aleph_0, the size of Nat 2) aleph_1, the size of Reals 3) ..(we won't have to use this jar or higher jars).. Now that the jars are clear, whenever asked to measure the size of a set, * guess which jar works * then use the S-B theorem to show a bijection, that then shows that the set in question fits that jar So would you guess that there is a correspondence between RE, the set of REs viewed as strings, and Nat? If so, try to find if you can find these : RE -- f : 1-1, total, into map --> Nat (Total = Every RE must be mapped from. 1-1 = non-collapsing maps.) Nat -- g : 1-1, total, into map --> RE (Total = Every Nat must be mapped from. 1-1 = non-collapsing maps.) Then you would write down |RE| = aleph_0 If it does not work, you would try to write RE --> Real and Real --> RE, and so on. Take a guess; which aleph seems to be sufficient (think of C progs <-> Nat). > And how can I > express a conclusion based on the SB theorem as a cardinal number > since it only proves a bijection exists? Answered above. 11/29/11: ======================================================= I supplied the wrong solution key to Asg 8, question 4, part 4, and the TAs may have graded as per my key. I have now updated the solution online. The question was "a regular set can have a non-regular superset". The answer is obviously 'yes'. I somehow wrote the solution key by mis-reading the question as "any regular set can have a non-regular superset" (for which the answer is 'no'). If you suffered from this erroneous grading, plz drop teach-cs3100 a note. 11/29/11: ======================================================= > Which handin folder do I turn in the ProjectWebsite.txt > file which has the url to our project website? asg10, asg10L1, or asg10L4? Please use asg10. I'll collect all the submissions by tomorrow midnight. ======================================================= 11/11/11: > Class notes 18, page 9; What does =>* mean? Zero or more derivations ======================================================= 11/11/11: # in Question 5 is NOT epsilon. It just is a symbol within Sigma. Sigma NEVER contains Epsilon which is the notation for an empty string. This is the reason why I had said that the language of T is 0...0 # 0...0 where # is just a plain old terminal character - much like 0, 1, 2 etc. ======================================================= 11/11/11: Pumping Lemma recap: Consider a language L = {0^n 1^n | n >= 0} It is not regular. To show that, we use the PL. Here is a theorem about a regular languages X: ANY string in X that is long enough (>= "m" in length, where m is a variable denoting the # of states that X's minimal DFA has) has a pump 'y' of some unknown (but non-zero) length. We are going to suppose that L, above is regular, and see what happens. If L is regular, it has a minimal DFA of m states. So ANY string >= m in length has a pump. Here is the creative part for picking a string w: (1) w must be in L. Does not matter which one w is. So long as #2 below "works", your choice of w was good enough (in fact, great!) (2) You gotta get out of L by pumping w. POOR CHOICE for (1): Pick w = 0^{m div 2 + 1} 1^{m div 2 + 1} * Clearly inside L * BUT the pump can be in the 0's only, in the 1's only, or straddle the 0's and 1's * Too many cases SMART CHOICE for (1): Pick w = 0^m 1^m * Clearly inside L * The pump can be in the 0 portion only * Thus, the actual length of y does not matter * Just pump y up or down, and get out. Unlike the "U" versus "Y" problem, the condition to get out of L is very easy here. For the "U" versus "Y" problem, what made it so hard was not so much as to GET INSIDE the language. The hardness was to GET OUTSIDE the langugage by pumping. Getting OUT in that case meant "achieve EQUAL 0s and 1s". ======================================================= 11/11/11: Since this is a late msg, plz do it only as a courtesy and to look meaningful: Q1 : L2CFG_ParseTreeAccept.pdf and L2CFG_Reject.pdf Q2: L2PDA_accept.pdf and L2PDA_Reject.pdf Q3: L2PDAfromCFG_Accept.pdf and L2PDAfromCFG_Reject.pdf Q4: Q4.pdf Q5: Q5.pdf ======================================================= 11/10/11: S --> (WS | @ W --> (WW | ) Please help us with our induction steps. -- I was expecting this question, so now an answer + hints: State some property P_S about S and also separately about W (call it P_W). We have: P_S depends on P_W and P_W fortunately depends only on P_W So prove something good about W through induction (whatever W's contract is). Call it P_W. Now assume P_W and prove P_S through induction. ======================================================= 11/9/11: I've put a PCP solver for your use under L21. It's also available on lab3-20 (for instance) at ~cs3100/PCPSolver_ver3/ (full sources). The binary is in that folder as pcp. To run it, make sure the above is in your path and type "pcp -i input.txt". Read README there. A good PCP project will involve these: 1) Play with the above solver 2) Read the theory behind PCP (I'll provide notes) 3) Implement your own heuristic solver in Python; of course, limiting search ======================================================= 11/7/11 > I've got another clarification question: > On 1. for the reject string you say "use any available method within JFLAP to show the inability to parse". The best I could find for this was to do the User Control Parser where you get to pick which production to use at each step and I went to a point where it was clear it wouldn't work, is that along the lines of what you were thinking? This will work. > Also: > Naming clarifications: For parts 2 and 3 shouldn't the reject string pdf names have "abcc" and not "abbc"? Good catch! Yes. ======================================================= One easy bug you can introduce in JFLAP's CFG tool: If you have a grammar S -> a B | b c D Enter it in JFLAP as S -> aB S -> bcD Not as "S -> a B | b c D" because it then looks for "a" "blank" "B" "blank" "vertical-bar" etc.. ======================================================= -------- Original Message -------- Subject: Asg 7 now due Thu 11:59pm Date: Tue, 01 Nov 2011 12:25:21 -0600 From: Ganesh Gopalakrishnan To: cs3100@list.eng.utah.edu 1) Asg7 now due Thu 11:59pm 2) Project proposal due next week Tue. This Thu, Nov 3rd, I'll be giving you a project proposal format + grading rubric so you know what to work toward. Projects themselves will be due last week of classes (date TBA) Ganesh ======================================================= 11/1/11: The bug in del_state_from_gnfa_N has been fixed. Hope this does it.. I bug-fixed and tested a lot . Hope this does it (I went thru all the steps requested of you and even went beyond, eliminating all states.. it worked). Yes there was a case overlooked in the code! It's tricky code (I can explain the patch). But I've also propagated all the online goodies and that took time. In particular, here are ALL the fixes done. I've tested all the byte-codes also and they work. All these updates + testing took most of the time. 1) pyc.tar.gz is good to load from l15 2) pyc-mac.tar.gz - ditto - good to load from l15 3) asg7-L.tar.gz - good to load from l15 4) Those who requested the "M" link -- please go back to your URL and you'll see a file "nfapy" there. Rename this to "nfa.py" and replace the nfa.py in the tarball you have with this. (name nfapy is to fool browsers who block loading nfa.py) 5) Those who requested the "S" link - ditto - you'll find "nfapy" in that link now. Follow above procedure. ======================================================= 11/1/11: del_state_from_gnfa_N (last question of the "S" part) has a known bug. It produces an incorrect NFA when state s4 is deleted. It's a matter of my finding some time and debug... but since we postponed this assignment today, I'll post a fix hopefully by tonight. The other bugs you can run into are the following (one popular pitfall): re2nfa does not return any value (other than null). So if you did NFA = re2nfa(...) , the NFA won't be one. It will be a null value. Instead, you can use NFA = yacc.parse('(a+b)*babb') and then carry on with this NFA. But then when you do del_state_from_gnfa... on this NFA, you will run into the bug when you delete state s4 Plz bear with me (I have meetings most of the rest of the afternoon and I'll debug amidst or after them) ======================================================= Oct 28, 2011 -- Asg7 Submission Clarifications General Facts: -------------- * When the final grades are posted, you can look for three headings: asg7, asg7a, and asg7b. People who did the L part will earn points in all three, the M group will earn in two, etc. * I think that making a URL is not easy for some of you (if you did it, fine, then submit a simple htm, html, or txt file containing the URL). Others can submit their writeup as a PDF. * Those who did S may please write-up all their answers in asg7S.pdf (or send a URL called asg7S.htm or asg7S.txt). In addition, for any code they wrote or modified, please submit the pertinent .py files also. You don't need to make these .py files runnable as a script. Expect the grader to load it into python3. * Those who did M may may please write-up all their answers in asg7M.pdf. For the L group, the name is asg7L.pdf (or corresponding URLs). Tasks and submission for S, M, and L: ------------------------------------- * For pickout_fn_defs.py, submit this .py file with updated comments in the source file, and also provide a brief writeup * For the n==4 case, submit the file endsinbabbmindfa.pdf containing the min DFA drawing * For the 'short description of the conversions', mention which functions get called during the conversions and what these functions do (just a few sentences). * For the exponential growth in min DFA sizes, indicate in your writeup the files that you generated confirming such a growth. You can try your own examples if you like. In your writeup, mention the file names and what you observed (briefly). * For the del_state_from_gnfa_N, submit the PDF of the intermediate NFAs (suitably named). Mention the names of these NFA in your writeup. Have a sentence or two in your writeup that confirms that the NFA appear to be correctly constructed after each state elimination. * For the M and L task of fixing reparse.py , you are required to add some code to the parsing rules (some parsing rules have code, some don't -- look for the missing "action parts" that make the NFAs). Write the missing code; then demonstrate that your fixed reparse.py is working, by testing it on two REs that exercise the code you wrote into reparse.py. The test results should be in the form of PDF drawings generated from REs, and a brief writeup (a few sentences explaining the code additions). * For the L group members who write nfa2dfa and minDFA, again they should test and show that their own code is working. This they do by running tests that produce machines and producing a PDF of the machines. Then these members writeup a description of their algorithms (succinctly) in their writeup. They also provide their code .py files. ======================================================= Oct 27, 2011 Asg8 is due 11:59pm Thu 10/27. I've updated Notes18. I've also put up all the JFLAP files for today's examples on the class webpage. The CFG to PDA conversion works fine now (I had put some blanks between symbols, and JFLAP was looking for blanks to be typed in..). Please load these JFLAP files into JFLAP, and experiment them -- before you come to class on Tue; you'll then really follow the lecture. ======================================================= Oct 25, 2011 I typo-fixed asg8 to say that "there exists" is a compact way to write repeated DISJUNCTIONS. (not repeated conjunctions) ======================================================= Oct 23, 2011 Someone just pointed out that remindfa.py wasn't in asg7-L.tar.gz . I just updated that. I also made sure that those who seek the "small" and "medium" options also have the right files. I could have overlooked something. So please make sure these, depending on your options. If you accidentally got more than you were supposed to, please write (rewrite) those codes. L : your minDFA.py and nfa.py will miss the DFA minimizer and the NFA->DFA routine details. You will also find reparse.py missing some of the "action" parts for some productions M : you will miss only the things in reparse.py - you'll get the rest S : you will be getting everything mentioned above On Tue, I'll be going through context-free grammars and parsing. Please read the notes already placed online. I'll also take some PL questions. We can write some parsers right in class, using ply. This will allow the "M" and "L" seekers to understand how to do their "parser action" parts. ======================================================= PYC for MACs I've kept a pyc-mac.tar.gz tarball under l15. This will help mac users use the byte-codes for all the demos I ran yesterday. Mac users may need to install Graphviz and Dot - both available from http://www.graphviz.org/Download_macros.php --