$1.[$Points $20]$ Regular expression and explain your answer.

a$.[$Points $5]$ Write a regex to match filenames that end with $.$txt or $.$pdf or $.$rtf$.$

b$.[$Points $5]$ Write a regex to match dates in the format DD$-$MM$-$YYYY or DD$/$MM$/$YYYY$.$

c$.[$Points $10]$ Write a regex to extract US phone numbers from a text. The phone numbers can be in the format $(123)456-7890$ or $123-456-7890.$

$2.[$Points $40]$

a$.[$points $20]$ Given the following text documents, apply the text normalization process to get a normalized text. Assume your text normalization process contains the following steps: lowercasing, removing punctuation, tokenization, removing stop words, and stemming. Determine tokens, vocabulary, and types. Please show each step for each document. Build your combined tokens and vocabulary from the given documents, and determine the total number of types, vocabulary, and tokens.

Doc $1$: "She sells sea shells by the seashore."

Doc $2$: "How much wood would a woodchuck chuck if a woodchuck could chuck wood?"

Doc $3$: "A journey of a thousand miles begins with a single step."

b$.[$points $20]$ Write a program that normalizes your text, list down the tokens and vocabulary and finally determines the total tokens, vocabulary, and types. Please follow the above steps appropriately in your code so that you can verify your $2$a$)$ answer.

$3.[$points $40]$ We know how to compute the similarity distance between two given strings using the edit distance algorithm.

a$.[$Points $20]$ Compute the edit distance for the following strings. Show the initial matrix that converts empty strings to another string $($given the example below$),$ and finally, show the distance for the examples.

String $1$: kitten

String $2$: sitting

b$.[$points $20]$ Write down the code to compute edit distance and verify the above answer. Your code should print the distance matrix in each step.