Next: Hints. Up: The Assignment Previous: Exercise 3

Exercise 4

The goal of this exercise is to write a desk calculator for regular languages. The user can
• either define a regular language by means of a regular expression,
• or submit a query about a defined language.
The representation of a defined language in the desk calculator is a finite automaton. Nota bene. We assume in the rest of the text that these automata are deterministic and complete (leading to the use of an error state). However you can use non-deterministic automata with or without instantaneous transitions. In that case you should adapt the specifications of the desk calculator.

The syntax of the definition of a language is

variable := language
where
• variable stands for an identifier (use the pattern of the second exercise)
• language is of one of the six forms
• language language
• language language
• language
• ( language )
• variable
• { expression }
where expression is a regular expression (in the sense of the course) over the alphabet consisting of the lower cases letters and the digits.

The possible queries are

The in
query which asks whether a word belongs or not to a language. The syntax is
"word" in language
where word is a word (in the mathematical sense) over and in is a keyword.
The states
query which asks what are the states of the automaton representing the language. The syntax is
states language
The initial
state query which asks what is the initial state of the automaton representing the language. The syntax is
initial language
The finals
query which asks what are the final states of the automaton representing the language. The syntax is
finals language

Here's a session with such a desk calculator. The prompt for the input line is ? and the prompt for the output line is =.

? L1 := {a(a|b)*}
= defined L1
? L2 := {(a|b)*b}
= defined L2
? L3 := L1.L2
= defined L3
?  "abba" in L3
= false
?  "abbab" in L3
= true
? states L3
= [0,1,2,error]
? initial L3
= 0
? finals L3
= [2]
? transitions L3
= (0, a, 1), (0, b, error), (1, a, 1),
(1, b, 2), (2, a, 1), (2, b, 2)

We give now a more detailed description of the possible commands by illustrative examples.

L1 := {a}
Assigns L1 to the language consisting of the single word a.
L2 := L1*
Assigns L2 to the star of the language L1. Hence L2 consists of all possible sequences of a, including the empty word.
L3 := L1.L2
Assigns L3 to the product of the languages L1 and L2. Hence L3 consists of all possible sequences of a, except the empty word.
L4 := {b}
Assigns L4 to the language consisting of the single word b.
L5 := L1|L4
Assigns L5 to the union of the languages L1 and L4. Hence L5 consists of the words a and b.
"" in L3
Returns true iff the empty word belongs to L3. In our context the answer will be false.
"aaa" in L3
Returns true iff the word aaa belongs to L3 which is the case in our context.
states L5
Returns a list of the states of the automaton representing L5. This could be [0, 1 , error].
initial L5
Returns the initial state of the automaton representing L5. This could be 0.
finals L5
Returns the final states of the automaton representing L5. This could be [1].
transitions L5
Returns the transitions of the automaton representing L5. This could be (0, a, 1), (0, b, 1), (1, a, error), (1, b, error).

Subsections

Next: Hints. Up: The Assignment Previous: Exercise 3
Marc Moreno Maza
2004-12-01