| Week | Tuesday | Thursday |
|---|---|---|
| Week 1 (09/02-09/06) | 1, 2 | 3 |
| Week 2 (09/09-09/13) | 4.1-4.3 | 4.4-4.5 |
| Week 3 (09/16-09/20) | 5.1 | 5.1 |
| Week 4 (09/23-09/27) | 5.2 | 5.3-5.7, Coding |
| Week 5 (09/30-10/04) | Midterm 1 | 6.1, 6.2 |
| Week 6 (10/07-10/11) | 7 | 7 |
| Week 7 (10/14-10/18) | Break | 7 |
| Week 8 (10/21-10/25) | 8 | 8 |
| Week 9 (10/28-11/01) | 9 | 9 |
| Week 10 (11/04-11/08) | 9 | Midterm 2 |
| Week 11 (11/11-11/15) | CFGs | CFGs |
| Week 12 (11/18-11/22) | CFGs | PDAs |
| Week 13 (11/23-11/29) | PDAs | Thanksgiving |
| Week 14 (12/02-12/06) | Review | Review |
containsGAGA, yes, longerThan1K, maybeLoop.countLines program; programs as input to other programs.yesOnString. Try at various inputs (group work Figure 3.4).exec, which takes a Python file and executes it. Can we use it to implement the behavior described by yesOnString (group discussion)?yesOnSelf. (group work Figure 3.5).yesOnSelf using yesOnString as a helper.notYesOnSelf. Think through what happens when notYesOnSelf is run with input the earlier programs, as well as itself. (group work).crashOnString, crashOnSelf, weirdCrashOnSelf.noOnString, noOnSelf.noOnSelf and notYesOnSelf equivalent programs, if they existed?noOnSelf as for notYesOnSelf?yesOnString cannot exist.isPrime in Moodlexs and increments its value by 1 (transducer).reverseBinaryDecrementer machine (should reject if the input is the number 0) and construct its state diagram.countCs Turing machine. Start by describing these helpers:
prependxprepend0incrementReverseBinarymoveHeadToNumberStartmoveHeadToStringStartdeleteString.tm files. (See also Fig. 5.19).tm file. Include a state diagram.universal.py and how it works.IsOdd and LastDigitIsEven problems, and solving IsOdd via LastDigitIsEven.GAGAOnString and proving it is undecidable via a reduction from YesOnString:
YesOnString to instances of GAGAOnString.altersYesToGAGA.yesOnString to containsGAGAOnString.IntOnString: It takes two strings \(P\), \(I\) as input, and outputs "yes" if \(P\) is a program and \(P(I)\) is a non-negative integer string (i.e. containing only digits). Similarly to what we did for GAGAOnString, show how YesOnString can be reduced to IntOnString.yesOnEmpty, yesOnAll, yesOnSome.ignoreInput.ignoreInput.py to write yesOnString using yesOnEmpty as a helper.yesOnString to yesOnEmpty or yesOnSome or yesOnAll. Sequence diagrams visual.haltsOnString, haltsOnEmpty, haltsOnAll, haltsOnSome.GAGAOnString to show a reduction from yesOnString to haltsOnString.haltsOnString to haltsOnEmpty. Include code and sequence diagram.IsEven? Explain.Computes_F for a computational problem F.F is a computable problem, then Computes_F is in fact uncomputable.ComputesOneOf_S.or”and”aab or ac (in any order). For example: aabacacaab would be accepted. Use as few states as possible (doable with 5).aab and ac earlier.Sentential forms
Origin of name “context-free”
Group activity: For the following grammar and list of strings, produce derivations of those strings from the grammar, as well as corresponding parse trees:
S -> T | E + T
T -> F | T * F
F -> v | nStrings:
v * n
v + v + n
n * v + v(Due Tue 12/4 4pm in LYN110)
abcba.(()(()()))).{ i, e } with rules S-> epsilon | SS | iS | iSe. Follow the standard algorithm for determining the PDA of a CFG, and not some other way. Write out the complete PDA diagram, including the expanded form of the “loops” corresponding to production rules.(Not to turn in)
We define the language of “L-values” as follows:
v,n,[,].v.L[I], where L is an arbitrary L-value and I is the “index”, described below:I can be either an integer (represented by n) or another L-value expression.Here is an example string that this grammar should be able to generate: v[v[i][v]].
L for the start variable, and I for the index variable. You will need 4 production rules.v[v[i][v]].X, and 6 production rules total.v[v[i][v]] in this grammar.v[v[i][v]] and this new grammar.