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