Instructor | Alley Stoughton |

Phone | 785.341.3041 |

alley.stoughton@icloud.com | |

Personal Website | alleystoughton.us |

Course Website | alleystoughton.us/150-efl |

Class Sessions | MW 4:30-5:45 p.m. Halligan 106 |

Office Hours | M 2-3 p.m. Halligan 111A, W 1-3 p.m. Halligan 106 |

The subject of formal language (automata) theory is traditionally
taught as a paper-and-pencil mathematics course, even though it is
largely concerned with algorithms on the subject's formalisms: regular
expressions, automata, grammars and Turing machines. In contrast,
this course will approach the subject in a way that balances proof
with *experimentation*, carried out using the Forlan toolset, which
implements the algorithms of formal language theory, and has been
developed by the instructor over the last decade. Forlan is embedded
in the functional programming language Standard ML, a language whose
notation and concepts are similar to those of mathematics. It is
strongly typed and interactive, properties that make sophisticated
experimentation robust and enjoyable.

This course complements, and may be taken before or after, COMP 170 (Computation Theory). Prerequisite: COMP 15 (Data Structures) and MATH 22 (Discrete Mathematics).

At the Spring 2012 Course Preview Event, I gave a pitch for taking this course.

We will be using the Spring 2012
draft of my textbook on formal language theory, entitled
*Formal Language Theory: Integrating Experimentation and
Proof*. The book will be posted in installments,
as the semester progresses.

You may find it useful to also study the related sections of another book on formal language (automata) theory. Note, however, that the notation and definitions used by any particular book won't be identical to the ones we'll be using.

Many of the algorithms that we will study are implemented as part of the Forlan toolset — a collection of tools for experimenting with formal languages that I've been developing since 2001. Forlan is implemented as a set of Standard ML (a functional programming language) modules. It's used interactively. In fact, a Forlan session is nothing more than an SML session in which the Forlan modules are available.

As the course progresses, you'll learn how to use Forlan, and you'll be using it when solving some of the homework exercises.

Forlan is available on the Department of Computer Science's Linux
system as `~stough/bin/forlan`. You should either
add `~stough/bin` to your shell's search path, or copy
`~stough/bin/forlan` to your own `bin` directory.
(E.g., if your shell is `bash`, put

declare -x PATH=~stough/bin:$PATH

in the file `.bash_profile` of your home directory.)

See the Forlan website for instructions for installing Forlan on personal computers.

The best way to run Forlan or SML is as a sub-process of the Emacs text editor, using the SML mode for Emacs. On the Department of Computer Science's Linux system, you can make SML mode available by putting the line

(load "/h/stough/emacs/sml-mode-4.1/sml-mode-startup")

in the file `.emacs` of your home directory.

JForlan, a Java program for
creating and editing Forlan automata and trees, is available on the
Department of Computer Science's Linux system
as `~stough/bin/jforlan`. You should either
add `~stough/bin` to your shell's search path, or copy
`~stough/bin/jforlan` to your own `bin` directory.
(Otherwise `forlan` won't be able to find `jforlan`.)

When preparing solutions to assignments, you may wish to make use of the LaTeX document prepartion system. LaTeX handles mathematics very well, and is widely used by academic computer scientists.

There will be seven problem sets, each worth 100 points, plus a final project, worth 300 points.

Each assessment unit will be graded using the following 100 point scale: A+ (100), A (92), A- (84), B+ (76), B (68), B- (60), C+ (52), C (44), C- (36), D+ (28), D (20), D- (12), F (0). (E.g., a grade of 80 points should be thought of as being halfway between a B+ and an A-.)

Late work will be assessed a penalty of 20% during the first twenty-four hours. Work that is more than twenty-four hours late will not be graded.

I will take the elegance and simplicity of your work into account when doing grading.

I reserve the right to award extra credit to students who find errors in, or suggest improvements to, course materials.

A student's grade for the course will be the letter (possibly followed by a + or -) whose value is nearest to the weighted average of the grades of the student's problem sets and final project. Ties will be resolved by selecting the better of the two grades.

Students should read the Tufts brochure on academic integrity located at:

http://uss.tufts.edu/studentaffairs/judicialaffairs/Academic%20Integrity.pdf

The work that you hand in must be your own. You may discuss assignments with others, but you may not base your work on other people's work.

I will often communicate with the class by email, and so it is important that you read your email frequently.

- Session 1: January 23
- Session 2: January 25
- Reading: Preface and Chaper 1
- Slides from Section 1.2 (print)
- Slides from Section 1.3 (print)

- Session 3: January 30
- Reading: Chapter 2
- Slides from Section 1.3 (print)
- Problem Set 1
- Slides from Section 2.1 (print)

- Session 4: February 1
- Slides from Section 2.2 (print)
- Section 2.3: Introduction to Forlan

- Session 5: February 6
- Reading: Section 3.1
- Slides from Section 3.1 (print)
- Slides from Section 3.2 (print)

- Session 6: February 8
- Reading: Section 3.2
- Slides from Section 3.2 (print)

- Session 7: February 13
- Session 8: February 15
- Reading: Section 3.3
- Slides from Section 3.3 (print)
- Slides from Section 3.4 (print)

- Session 9: February 22
- Reading: Sections 3.3 and 3.4
- Slides from Section 3.3 (print)
- Slides from Section 3.4 (print)
- Slides from Section 3.5 (print)

- Session 10: February 23
- Reading: Sections 3.5 to 3.8
- Slides from Section 3.6 (print)
- Slides from Section 3.7 (print)

- Session 11: February 27
- Session 12: February 29
- Reading: Sections 3.9-3.11
- Slides from Section 3.10 (print)
- Slides from Section 3.11 (print)

- Session 13: March 5
- Session 14: March 7
- Reading: Section 3.12
- Slides from Section 3.12 (print)

- Session 15: March 12
- Class canceled due to non-attendance

- Session 16: March 14
- Reading: Sections 3.13 and 3.14
- Slides from Section 3.12 (print)
- Slides from Section 3.13 (print)

- Session 17: March 26
- Reading: Section 3.15
- Slides from Section 3.13 (print)
- Slides from Section 3.14 (print)

- Session 18: March 28
- Session 19: April 2
- Session 20: April 4
- Session 21: April 9
- Reading: Sections 4.1-4.5
- Slides from Section 4.5 (print)
- Slides from Section 4.6 (print)

- Session 22: April 11
- Reading: Section 4.6
- Slides from Section 4.6 (print)
- Slides from Section 4.7 (print)
- Slides from Section 4.8 (print)
- Slides from Section 4.9 (print)

- Session 23: April 18
- Reading: Section 4.7-4.9
- Slides from Section 4.10 (print)

- Session 24: April 23
- Reading: Section 4.10
- Slides from Section 5.1 (print)

- Session 25: April 25
- Reading: Section 4.10
- Slides from Section 5.1 (print)
- Slides from Section 5.2 (print)
- Slides from Section 5.3 (print)

- Session 26: April 30
- Project Presentations

- Problem Set 1
- Model Solution to Problem Set 1
- Problem Set 2
(
`ps2-framework.sml`) - Model Solution to Problem Set 2
(
`ps2-explain.sml`) - Problem Set 3
- Model Solution to Problem Set 3
(
`ps3-prob1.sml`) - Problem Set 4
- Model Solution to Problem Set 4
(
`ps4-dfa`,`ps4-prob2.sml`) - Problem Set 5
- Model Solution to Problem Set 5
(
`ps5.sml`,`ps5-test.sml`) - Problem Set 6
- Model Solution to Problem Set 6
(
`ps6-gram1`,`ps6-gram2`,`ps6.sml`) - Problem Set 7
- Model Solution to Problem Set 7

Alley Stoughton (alley.stoughton@icloud.com)