{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 2: 2017/01/23-27" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from tock import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Monday reading\n", "\n", "Read 1.1.\n", "\n", "Sipser uses an automatic door to illustrate a finite automaton. (The door is the type that swings open toward you, not the type that slides open.) This example is good because its state is something visible. But this automaton doesn't have accept states, because the input string has no end and the automaton's job is not to accept or reject strings. So the door is best thought of as an analogy more than a strict example.\n", "\n", "The section \"The regular operations\" is slightly unusual. These closure properties are important, and where he's going with this is that these closure properties will be used to prove that any regular expression can be compiled into a finite automaton. But using DFAs, this proof is not easy and he gives up halfway. Sipser uses this as a motivation for nondeterminism, which is introduced in the next section. The proof of both Theorem 1.25 and 1.26 will turn out to be very easy.\n", "\n", "On the other hand, the proof of Theorem 1.25 has a footnote (3) regarding closure under intersection. This is an important result and the Cartesian product construction _is_ the standard way to prove it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Tuesday class" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Deterministic finite automata\n", "\n", "In the first class, I said that we would study a sequence of kinds of \"computers\" leading up to Turing machines. Today we'll look at the simplest of these, finite automata, which are only allowed to make a single left-to-right pass through the input.\n", "\n", "- The machine is fed a paper tape with a string written on it.\n", "- At each time step, it reads one symbol and moves one square to the right.\n", "- It has only a finite number of states (another way of saying this: it uses only $O(1)$ memory).\n", "- When it reaches the end of the string, it decides whether to accept or reject the string.\n", "\n", "In lecture notes I'll be using a toolkit called [Tock], which displays and runs automata inside Jupyter notebooks. You are welcome to use it to tinker with automata or to write your homework assignments.\n", "\n", "Tock reads files in CSV format (or in a graph format called TGF):\n", "\n", "[Tock]: https://github.com/ND-CSE-30151/tock" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " , 0 , 1\r\n", ">q1 , q1 , q2\r\n", "@q2 , q3 , q2\r\n", " q3 , q2 , q2\r\n" ] } ], "source": [ "%cat dfa-m1.csv" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [], "source": [ "m1 = read_csv('dfa-m1.csv')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then you can display it as a table or as a graph:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", " | 0 | \n", "1 | \n", "
---|---|---|
>q1 | \n", "q1 | \n", "q2 | \n", "
@q2 | \n", "q3 | \n", "q2 | \n", "
q3 | \n", "q2 | \n", "q2 | \n", "