Repeat your evaluation in parts a and b on this expanded version of regular expressions.
Regular expressions are a compact way to define a search pattern. They were first developed by the mathematician Stephen Cole Kleene in 1951 and have since found wide implementation in computer applications. These expressions can be evaluated as a formal language, where a given search expression (or pattern) is compared to an input string. The algorithm will accept the input string if the pattern is matched, and reject the input if the pattern is not matched. In order to analyze this type of language, we will define the minimal functionality needed to implement regular expressions. First, we define the base elements in the system: The null character 0 The empty string a Literal characters from the set of all characters a Next, we will define three operations that can be performed on regular expressions, to generate new regular expressions: (RS) : concatenation. Example: for R = {0,00} and S = 1, 11, RS = {01,001, 011, 0011} (RUS): alternation. Example: for R= {0,00} and S = {1, 11}, RUS = {0,00,1, 11} (R+) : the Kleene star, which denotes the set of all strings that can be made by concatenating any finite number of strings from the set R. Example: for R = {0,1}, R* is the set of all finite binary strings (including the empty string e). . (a) [5 points] What level of the Chomsky hierarchy is the grammar described above, and why? (b) [5 points) Is this system guaranteed to halt in either the "accept" or "reject" state (i.e. not form an infinite loop)? Why or why not? (c) [5 points] The POSIX standard for regular expressions adds additional operators to the minimal set given above. In particular, it adds the following wildcard operators: .: wildcard matching a single character. Example: a.c matches {aac, abc, acc ...} * : wildcard matching zero or more characters. Example: a*c matches {ac, abc, abbc, ... } {m,n} : matches the preceding element at least m, but not more than n, times. Example: a{1,2}b matches {ab, aab} only Repeat your evaluation in parts a and b on this expanded version of regular expressions. (d) [5 points] Some versions of regular expressions parsers, such as those in Perl, Python, and most versions of SQL, add yet more operators to the language. In particular, they add the backreference operator: (.+) : backreference Example: (-+)\1 matches repeated pairs of elements in the data, and (.+)\2 matches repeated triples of elements in the data . Regular expressions are a compact way to define a search pattern. They were first developed by the mathematician Stephen Cole Kleene in 1951 and have since found wide implementation in computer applications. These expressions can be evaluated as a formal language, where a given search expression (or pattern) is compared to an input string. The algorithm will accept the input string if the pattern is matched, and reject the input if the pattern is not matched. In order to analyze this type of language, we will define the minimal functionality needed to implement regular expressions. First, we define the base elements in the system: The null character 0 The empty string a Literal characters from the set of all characters a Next, we will define three operations that can be performed on regular expressions, to generate new regular expressions: (RS) : concatenation. Example: for R = {0,00} and S = 1, 11, RS = {01,001, 011, 0011} (RUS): alternation. Example: for R= {0,00} and S = {1, 11}, RUS = {0,00,1, 11} (R+) : the Kleene star, which denotes the set of all strings that can be made by concatenating any finite number of strings from the set R. Example: for R = {0,1}, R* is the set of all finite binary strings (including the empty string e). . (a) [5 points] What level of the Chomsky hierarchy is the grammar described above, and why? (b) [5 points) Is this system guaranteed to halt in either the "accept" or "reject" state (i.e. not form an infinite loop)? Why or why not? (c) [5 points] The POSIX standard for regular expressions adds additional operators to the minimal set given above. In particular, it adds the following wildcard operators: .: wildcard matching a single character. Example: a.c matches {aac, abc, acc ...} * : wildcard matching zero or more characters. Example: a*c matches {ac, abc, abbc, ... } {m,n} : matches the preceding element at least m, but not more than n, times. Example: a{1,2}b matches {ab, aab} only Repeat your evaluation in parts a and b on this expanded version of regular expressions. (d) [5 points] Some versions of regular expressions parsers, such as those in Perl, Python, and most versions of SQL, add yet more operators to the language. In particular, they add the backreference operator: (.+) : backreference Example: (-+)\1 matches repeated pairs of elements in the data, and (.+)\2 matches repeated triples of elements in the data
