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