Language Processors (F29LP)

Course overview

Welcome to the Language Processors webpage. In a nutshell, this course says:

“What is a computer language, really? Well, let’s generate the language by recursive rules (or automata—same thing) … then let’s give the language semantics …”

I’m co-lecturing this course with my colleage Gudmund Grov.

Lecture and lab times

- Mondays at 14:15 in EM3.36.
- Tuesdays at 10:15 in EM2.44.
- Tuesdays (lab) at 14:15 in EM2.50 (or possibly DB115).
- Today (Tuesday January 10) there will be a lecture at 14:15 in DB115 (and not a lab).

Labhelpers’ rules

  1. Submit your work in pdf format.
  2. Include in each document: Your name. Your regno or username. A clear statement of what questions (you think) you are answering.
  3. Include in the filename of the document: Your name. A clear statement of what questions you are answering. For example: Gabbay-Jamie-QI.pdf.
  4. Follow the following format: Number of question. Statement of question. Your answer. And make sure the statement of the question is clearly separated from your answer.
  5. If you need to include a jpeg in your pdf (e.g. a photo of a hand-drawn graph) then make sure it’s readable.
  6. But don’t hand-draw graphs; this is the 21st Century. Use LibreOffice Draw, Google Draw, or some similar program.
  7. Resubmission is at the discretion of the labhelper. Good work more than 24 hours before the deadline might invite feedback and an invitation to resubmit. Poor work on the day of the deadline, may not. Work that respects these rules may invite resubmission; work that does not respect these rules may not. Rule of thumb: if you make it easy for the labhelper to help you, then he will.
  8. You can book a slot with a labhelper in advance. Got problems? Ask Pierre or Vito or myself to allocate you five minutes so they know.

Please also read the following:
- How to answer a programming question.
- Some comments on how to answer the question.

Lectures

The videos will be updated as they are created!

Lecture of Monday 9 January at 14:15
Watch it and/or read the slides for lecture 1.
See the regex resources.
Lecture of Tuesday 10 January at 10:15
Watch it and read lecture 2, on formal grammars.
Lecture of Tuesday 12 January at 14:15
Watch it and read lecture 2, on formal grammars.
Lecture of Monday 16 January at 14:15
Watch it and/or read the slides for lecture 2.
See the regex resources.
Lecture of Tuesday 17 January at 10:15
Watch it and read lecture 3, on formal grammars.
Lecture of Monday 23 January at 14:15
Watch it and/or read the slides for lecture 4, on Deterministic Finite Automata (DFAs).
Lecture of Tuesday 24 January at 10:15
Watch it and read lecture 4.
Lecture of Monday 13 February at 14:15
Watch it and read lecture 5.
Lecture of Tuesday 14 January at 10:15
Watch it and read lecture 6.
Lecture of Tuesday 14 January at 14:15
Watch it and read lecture 6.

See also last year’s lectures.

The Rules

1. Turn up!
2. Understand lecture materials as you get them.
3. A student who thinks “I don’t understand this now; I’ll sort it out during the holidays” is in denial (look at 1m03s).
4. Rules 1-3 above apply especially to those who believe rules 1-3 above don’t apply to them.

List of lecture slides

lecture-1.pdflecture-2.pdflecture-3.pdflecture-4.pdflecture-5.pdflecture-6.pdf

Exercises (Labs) …

… are here.

Tutorials

- Tutorial I.
- Tutorial II.

Regex resources

- debuggex, which draws pictures of the regex (see this example), is fantastic.
- The lightweight regexpal and rather heavier-weight regexr and regex101, which you could test on The Jabberwocky.
- A page on regular expressions in Perl.
- This tutorial on regular expressions.
- This advanced page on sed.

Automata resources

Lewis Maitland kindly drew my attention to these two great tools:
- An automaton simulator.
- A tool for converting a regex to an NFA or DFA.
- For examples of automata “in nature”, see the following:

If you find an online tool for generating parse trees given a grammar, or for converting between context-free grammars, PDAs, and parsers, then please let me know.

The following are not automata but they’re so funny, I’ll mention them anyway:

Grammar resources

- See the online production grammar tool.
- Jison converts context-free grammars to Javascript, you can try it online.
- Here’s quite a nice parse tree generator
- And here’s another

Other course resources

You might like to have a look at:

- I really like bits of Jarkko Kari’s notes on Automata and formal languages (from his course at the University of Turku in Finland).
- Eitan Gurari’s course notes on formal grammars (from Ohio State University in the USA).
- Andrew Black’s course on computational structures is a model of online accessibility.
- Computer science degrees often include a course on automata and formal languages. It is often called “Automata and Formal Languages”. Just search Google for automata and formal languages solutions, and explore.
- The Wikipedia page on formal languages.
- The Wikipedia page on the Chomsky hierarchy has a good cheat-sheet at the bottom.

Mock paper and 2014 exam

A mock paper for my half of the course is available, along with the 2014 exam and resit:
- Without solutions (do this first).
- With solutions.
- The exam and resit from last year are in Vision under Learning Materials.

A bit about me

I am a researcher in theoretical computer science. My research is mostly in formal logic.
Everybody calls me Jamie but my name is actually Murdoch. You can contact me by e-mail on “gabbay at macs hw ac don’ttypethis uk”. My office is G.50 Earl Mountbatten Building.

The students …

… should be mostly third year undergraduate students.

If you don’t know what an undergraduate student looks like, think of minions, but less yellow.