Overview

Just to give a few examples:

If $L_1 = \{foo,bar,a,fright\}$, then $\text{chop}(L_1) = \{oo,ar,\lambda,right\}$

If $L_2 = \{ant,pant,fit,hit\}$, then $\text{chop}(L_2) = \{nt,ant,it\}$

In the homework for Lecture 12, you were asked to prove a result about the "chop" of a language, although I didn't give that name to it then. For language $L \subseteq \Sigma^*$, define the "chop" of $L$ as: \[ \text{chop}(L) = \{ w \in \Sigma^*\ |\ xw \in L \text{ for some $x\in\Sigma$} \} \] Your job was to prove that "if $L$ is accepted by an NDFA, then $\text{chop}(L)$ is accepted by an NDFA". Note that I let you cheat — I let you assume that the "NDFA accepting $L$" doesn't have $\lambda$-transitions out of the start state. Given that, the natural way to do this is to produce an algorithm with the specification:
Input: NDFA $M = (Q,\Sigma,\Delta,s,W)$, with no $\lambda$-transitions out of $s$
Output: NDFA $M'$ such that $L(M') = \text{chop}(L(M))$
This mini-project will build on that homework problem.

Part 1 - spot the flaw in the proof

Consider FlawedSolution1, which presents what purports to be an algorithm that meets the above specification along with what purports to be a proof of correctness for the algorithm. Both algorithm and proof are flawed. Your job for this part is to precisely identify and clearly explain the flaw in the proof. Note that this is different from proving that the algorithm doesn't work (which is your job in the next part). I'm telling you right now that the algorithm is bad, and because that's the case there must be a bug in the proof (you can't "prove" a falsehood). You need to find that bug in the proof and clearly explain how it is wrong. Note: You may find it easier to start thinking about Part 2 first.

Part 2 - prove the algorithm fails

Prove that the algorithm in FlawedSolution1 is bad, i.e. it doesn't always produce output that matches the specification. Note that this doesn't follow from the fact that the proof is bad — you can have an invalid "proof", and have the statement you tried to prove be true none-the-less. So you'll have to think: what will it take to prove categorically that this algorithm is flawed? Then you'll have to find such a proof, and give a careful presentation of it.

Part 3 - prove the whole enchilada

Provide a complete proof that:
If $L$ is accepted by an NDFA, then $\text{chop}(L)$ is accepted by an NDFA.
Note that by a "complete proof" I mean that you may no longer assume that $\lambda$-transitions out of the start state won't happen.

What to turn in

This "mini-project" will be done in groups of three (with special permission, group of two). Your group will submit three short videos (five minute max per video), each presenting a solution for one of the three parts. These could be narrated videos of work on a whiteboard or on paper, or something fancier if you are so inclined.
Rules
  1. Each video should be self-contained, i.e. not referring to either of the other videos.
  2. Each group member has to have a substantial role in all three videos - e.g. narrator, cameraman, scriptwriter, editor, board-drawer, etc.
  3. Each video must begin by introducing the three group members, and credit roles in the video either at the beginning or end (i.e. what each person did).
  4. This doesn't need to be super high-tech or fancy (I'm expecting cell-phone videos) but the audio needs to be clear and the camera-work steady and clear enough to easily make out anything on a board or paper you expect your audience to read.
  5. Your target audience should be a hypothetical person from SI340 who didn't do this project, but had at least scanned through FlawedSolution1 for five minutes before watching your video.
Honor
  1. For this assignment, work is intended to be done within the group only.
  2. For this assignment, you are allowed to discuss problems and solution strategies with folks from other groups. However, notes or any other record of what was discussed other than what's inside your brains must be destroyed when the discussion is finished, and you must wait at least 30 minutes before resuming work on your group's solutions. Obviously, such discussions must be documented.
  3. You have free license to discuss video-production issues and techniques.
Grading (rubric.html)
  1. the correctness of your results
  2. the clarity of your presentation
  3. creativity in your use of the video as a medium for explaining proof
  4. whether you meet a certain minimal threshold of AV quality
  5. extra credit for anything that looks exceptionally cool
Note: Expect at least one video from each group to be shown to the entire section in-class. We will (constructively!) discuss and evaluate the videos shown. Below is a sample video showing a low-tech, but hopefully clear and comprehensible, presentation. Sorry for the wiggly camera, but my videographer is only nine.

When and how to submit solutions

Final videos must be submitted by COB, 17 October. Details on how to submit to appear.