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 Moodlex
s 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:
prependx
prepend0
incrementReverseBinary
moveHeadToNumberStart
moveHeadToStringStart
deleteString
.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 | n
Strings:
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.