The programming language C adopted the convention of signalling the use of hexadecimal (base-16) numbers by...

Transcribed Image Text:

The programming language C adopted the convention of signalling the use of hexadecimal (base-16) numbers by using the prefix "Ox", followed by a non-empty sequence of the digits "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F" to represent the value of such numbers. This allows for a convenient representation of binary patterns that are multiples of 4 bits long (one hexadecimal digit for each four-bit group), e.g. OxA01E represents a 16-bit pattern, the "word" size of the machine for which C was originally developed. (a) Give a regular expression that characterises C's representation of hexadecimal numbers [6%] of arbitrary length, making use of hdigit as defined below. hdigit ('0'|'1'|'2' 1'3'1'4'1'5'1'6'|'7'1'8'1'9''A''B''C' | 'D' | 'E''F') (b) Translate the regular expression given in your answer to (a) into a Non-deterministic [7%] Finite Automaton (NFA), showing your working. (c) Translate the Non-deterministic Finite Automaton given in your answer to (b) into a [7%] Deterministic Finite Automaton (DFA), showing your working. (d) Using your answer to part (b) of this question, give a state-transition lookup-table for [5%] parsing identifiers. The programming language C adopted the convention of signalling the use of hexadecimal (base-16) numbers by using the prefix "Ox", followed by a non-empty sequence of the digits "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F" to represent the value of such numbers. This allows for a convenient representation of binary patterns that are multiples of 4 bits long (one hexadecimal digit for each four-bit group), e.g. OxA01E represents a 16-bit pattern, the "word" size of the machine for which C was originally developed. (a) Give a regular expression that characterises C's representation of hexadecimal numbers [6%] of arbitrary length, making use of hdigit as defined below. hdigit ('0'|'1'|'2' 1'3'1'4'1'5'1'6'|'7'1'8'1'9''A''B''C' | 'D' | 'E''F') (b) Translate the regular expression given in your answer to (a) into a Non-deterministic [7%] Finite Automaton (NFA), showing your working. (c) Translate the Non-deterministic Finite Automaton given in your answer to (b) into a [7%] Deterministic Finite Automaton (DFA), showing your working. (d) Using your answer to part (b) of this question, give a state-transition lookup-table for [5%] parsing identifiers.