Software for Matematisk Lingvistik

This is a collection of Prolog programs which can be used for practical exercises with the material from the course Matematisk Lingvistik. If you have comments on this software or know other sites with interesting software related to this course, mail to erikt@stp.ling.uu.se.

Working with this software is an optional part of this course. If you don't like programming in Prolog don't use this software. You cannot earn any credits for working with these programs.

Deterministic Finite State Automata

Chapter 17.1-17.1.2 of the Partee et.al. 1993 book will give you the background information for the material that is covered by this software.

The program dfaparse.p can be used to implement and determistic finite state automata. As an example of such an automaton you can use the program dfa1.p which defines an automaton that accepts all strings which consist of zero or more a's followed by zero or more b's.

The dfaparse program supplies the predicate consume/1 for testing if a string can be accepted by an automaton. Futhermore you can use the predicate produce/1 for producing a list of strings that are accepted by the automata. This predicate should be called with a variable as argument. The program recognizes the string e as the empty string.

This is an example of using the program:

$ prolog
booting, please wait...
SICStus 3 #3: Wed Feb 14 16:03:48 NFT 1996
| ?- ['dfa1.p'].
{consulting dfa1.p...}
{consulting dfaparse.p...}
{dfaparse.p consulted, 100 msec 19184 bytes}
{dfa1.p consulted, 120 msec 21232 bytes}
yes
| ?- consume(e).
yes
| ?- consume(ab).
yes
| ?- consume(ba).
no
| ?- produce(X).
X = e ? ;
X = a ? ;
X = b ? ;
X = ab ? ;
X = aa ? ;
X = bb ? ;
X = abb ?
yes
| ?- halt.
$

As you may have noticed you have to type a semi-colon to get extra alternatives from the produce/1 predicate. If you manage to get the example program running you can try to write automatons that accept the following languages and no other strings:

1. The language consisting of the string ab.
2. The language consisting of all possible strings containing a's and b's except for ab.
3. The language consisting of all strings containing a's and b's in which no sequence of successive a's has length longer than two.
4. An infinite subset of the language of the strings which contain an equal number of a's, b's and c's. The automaton that you construct here may not contain more than eight states.
5. A prime number is a natural number that has only itself and 1 as divisor. The language L is the language of strings over the alphabet {a} which contains n a's in which n is a prime number. Do you think that it is possible to construct a deterministic finite automaton that accepts this language? If you think it is possible then program the automaton or sketch how it should be constructed (you may need a large automaton!). Otherwise give a reason for why this is not possible.