Consider the regular expressions:

letter = a | b | c | d

LETTER = A | B | C | D

digit = 4 | 5 | 6 | 7 | 9

R1 = (LETTER | digit ) (letter digit)* (letter | digit)

R2 = (digit ) (letter* digit*)* (LETTER | letter)

R3 = (LETTER | digit ) (letter | digit)* (LETTER | digit)

R4 = (digit letter ) (letter* digit*) (LETTER)

Recall that, for a list of regular expressions, the function getToken() returns the next token from the input that matches one of the regular expressions. If there is more than one match, the longest match is returned. If there is more than one longest match, the token with the longest match that appears first in the list is returned. If there is no match, ERROR is returned. If the function getToken() is called mutliple times on input S until the end of input is reached, the sequence of tokens returned is the following (EOF refers to end of input): Then use the following table to get S.

input S: a5a5a5a5a55555aaA

Show your work in the worksheet. Please draw the table for the Longest prefix matching algorithm.