Tutorial Week 3 (Solutions)
Task 1. Here is one solution.
letter = [a-zA-Z]
email = letter+ ‘@’ letter+ ‘.’ letter+ ‘.’ letter+
Many others are possible.
Task 2. Here is pseudo-code that implements the requirements.
def scan ( input : String ) : Boolean = {
val init = 0 // This is the initial state
val error = 1 // State used to signal an error (not strictly
// necessary)
val accept = 2 // Accepting state.
val table = Array.fill ( 256, 3 ) ( error ) // Creating the table.
// 256 is the number
// of ASCII codes. 3
// the number of
// states. Every table
// element is set to error
for ( i <- 'a'.toInt to 'z'.toInt ) { // Setting non-error
table ( i ) ( init ) = accept } // transitions from the
// initial state
for ( i <- 'a'.toInt to 'z'.toInt ) { // Setting non-error
table ( i ) ( accept ) = accept } // transitions for
// lower-case letters from
// the accepting state
for ( i <- 'A'.toInt to 'Z'.toInt ) { // Setting non-error
table ( i ) ( accept ) = accept } // transitions for
// upper-case letters from
// the accepting state
var i = 0 // index to scan the input array
var state = init
while ( i < input.size ) {
state = table ( input ( i ) ) ( state ) // update state
i += 1 } // next character to be scanned
state == accept // returns true exactly when we leave the loop in
// the accepting state.
}
Note that this is not exactly a space-efficient solution.
Task 3. We only demonstrate how to add support for "Hello", the rest is similar. Most of the code for scan is unchanged, only the table (and acceptance) needs to be different, like so:
// We start with initialisation code that is unchange
// from Task 2's solution.
val init = 0
val error = 1
val accept = 2
val acceptHello = 7
val table = Array.fill ( 256, 8 ) ( error )
for ( i <- 'a'.toInt to 'z'.toInt ) {
table ( i ) ( init ) = accept }
for ( i <- 'a'.toInt to 'z'.toInt ) {
table ( i ) ( accept ) = accept }
for ( i <- 'A'.toInt to 'Z'.toInt ) {
table ( i ) ( accept ) = accept }
val h = 3
val he = 4
val hel = 5
val hell = 6
table ( 'H'.toInt ) ( init ) = h
table ( 'e'.toInt ) ( h ) = he
table ( 'l'.toInt ) ( he ) = hel
table ( 'l'.toInt ) ( hel ) = hell
table ( 'o'.toInt ) ( hell ) = acceptHello
var i = 0 // index to scan the input array
var state = init
while ( i < input.size ) {
state = table ( input ( i ) ) ( state ) // update state
i += 1 } // next character to be scanned
( state == accept || state == acceptHello ) // returns true exactly when we leave the loop in
// the accepting state.
// The rest (setting up variables i and state, the while loop ...)
// is unchanged