Instructor | Alley Stoughton |

stough@bu.edu | |

Personal Website | alleystoughton.us |

Course Website | alleystoughton.us/591-s2 |

Class Sessions | TR 12:30-1:45pm CAS 324 |

Problem Solving Sessions | T 6:30-7:30pm MCS 144 |

Office Hours | TR 2:30-4pm, MCS 134 |

Course Piazza | piazza.com/bu/fall2018/cs591s2 |

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 approaches the subject in a way that balances proof with
*experimentation*, carried out using the
instructor's Forlan toolset, which implements
the algorithms of formal language theory. Forlan is embedded in the
functional programming
language Standard ML (SML), a
language whose notation and concepts are similar to those of
mathematics. SML is strongly typed and interactive, properties that
make sophisticated experimentation robust and enjoyable. The course
features a rigorous approach to carrying out mathematical proofs,
focusing on basic set theory, definitional techniques including
various forms of recursion, and proof techniques including different
kinds of induction.

Prerequisites: CS 112 (Introduction to Computer Science 2) and CS 131 (Combinatoric Structures), or equivalent.

Here is a pitch for why you should consider taking this course.

- Course Syllabus
- Course Grading Function
- Forlan Project
- Textbook
- Forlan Manual
- LaTeX Document Preparation System

We will be using the Fall 2018
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. But, if you want to read ahead, you can also consult
the September 2012 draft.

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 problem sets. The best way to run Forlan or SML is as a sub-process of the Emacs text editor, using the SML mode for Emacs. We'll also be using JForlan, a Java program for creating and editing Forlan automata and trees.

See the Forlan website for instructions for
installing Forlan on personal computers. Forlan is also installed on
the CS Department's Linux
servers `csa1.bu.edu`, `csa2.bu.edu` and
`csa3.bu.edu`, which may be accessed either remotely or from
the Linux workstations in the CS Department's Computing Lab (Room 302
of 730 Commonwealth Avenue). When connecting to one of these servers
using the secure shell (`ssh`) command on Linux or macOS, you
must use the `-Y` option, so as to enable "trusted X11
forwarding". Otherwise, you won't be able to use JForlan. I.e., run
one of the commands

ssh -Y csa1.bu.edu ssh -Y csa2.bu.edu ssh -Y csa3.bu.edu

There will be seven problem sets, each worth 100 points, plus a final exam, worth 150 points. Problem set solutions will be submitted as hardcopies, either in class, at office hours, or via the course's CS Department drop box. But when a problem set involves writing Forlan code, that code must also be submitted via email to me (stough@bu.edu).

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.

The elegance and simplicity of your work will be taken into account when it is assessed. 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 exam. Ties will be resolved by selecting the better of the two grades.

You are responsible for reading and understanding BU's Academic Conduct Code (for undergraduates)

or the GRS Academic and Professional Conduct Code (for graduate students)

http://www.bu.edu/cas/files/2017/02/GRS-Academic-Conduct-Code-Final.pdf

The work you hand in must be your own. You may discuss problem sets with others in general terms, but you may not base your work on other people's work, and you may not show your draft work to others. If you use resources other than course materials when working on the problem sets, you must cite your sources. (You may, of course, share your draft work with myself and any other course staff.)

Incidents of academic misconduct will be reported to the Academic Conduct Committee (ACC). If the ACC finds a student guilty, punishment could range from a minimum of a grading sanction (e.g., dropping your final grade by one letter grade) all the way up to suspension or expulsion from the University.

I will often communicate with the class by email, and so it is
important that you read your email frequently. I'll be offering weekly
optional help sessions, in which I'll solve problems on the blackboard
and answer questions. They will be on Tuesdays from 6-7:15pm in MCS 144.
My office hours will be on Tuesdays and Thursdays from 2:30-4pm
in MCS 134. You can also make an appointment with me at an alternative
time. We'll be using Piazza for online
discussions. Visit

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

- Session 1: September 4
- Session 2: September 6
- Session 3: September 11
- Session 4: September 13
- Session 5: September 18
- Session 6: September 20
- Session 7: September 25
- Session 8: September 27
- Session 9: October 2
- Session 10: October 4
- Session 11: October 11
- Session 12: October 16
- Session 13: October 18
- Session 14: October 23
- Session 15: October 25
- Session 16: October 30
- Session 17: November 1
- Session 18: November 6
- Session 19: November 8
- Session 20: November 13
- Session 21: November 15
- Session 22: November 20
- Session 23: November 27
- Session 24: November 29
- Session 25: December 4
- Session 26: December 6
- Session 27: December 11

- 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
- Problem Set 4
- Model solution to Problem Set 4
(
`ps4-p2-dfa.txt`,`ps4-p2-testing.sml`) - Problem Set 5
- Model solution to Problem Set 5
(
`ps5-p3.sml`) - Problem Set 6
- Model solution to Problem Set 6
(
`ps6-p2-gram.txt`,`ps6-p2-testing.sml`) - Problem Set 7
- Model solution to Problem Set 7
(
`ps7-p3-orig-gram.txt`,`ps7-p3-even-01-dfa.txt`,`ps7-p3-find.sml`,`ps7-p3-elim.sml`,`ps7-p3-gen-len.sml`,`ps7-p3-gram.txt`)

- 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)