Here is part of the instruction:
Strings and Functions
In this lab you will develop a recursive function for performing a primitive type of regular expression matching.
Simple String Matching Algorithm
Define a matcher expression (ME)
Define a string s ϵ S to match an ME m iff
1. s is of length one, and m is either s or ‘.’, or
2. m is .*n and n matches some suffix of s, or
3. m is x*n and s can be decomposed into a string s1 followed by a string s2 such that
s1 is 0 or more occurrences of x and s2 matches n, or
4. m can be written as m1m2 and s as s1s2 such that m1 matches s1 and m2 matches
s2 based on one of the three conditions above.
Design an algorithm that takes a string s and ME m and returns whether s matches m. The main.c we provide contains a number of tests, but you should write some of your own test cases, in the spirit of the tests in our main.c. Make sure you consider corner cases.