Grep:pattern matching

### Program Information

Name: Grep:pattern matching
Domain: Algorithm
Functionality: Grep is a UNIX command-line utility program written in C, which performs the pattern matching.
Input: With an input file $''file.in''$ and a given input regular expression $RE_s$, MRs are used to generate follow-up regular expression $RE_f$ which is equivalent to $RE_s$.
Output: Since $RE_s$ and $RE_f$ are equivalent but different in format, their corresponding outputs $O_s$ and $O_f$ should be exactly the same as each other.

#### Reference

Spectrum-Based Fault Localization: Testing Oracles Are No Longer Mandatory https://doi.org/10.1109/QSIC.2011.20;
Metamorphic slice: An application in spectrum-based fault localization https://doi.org/10.1016/j.infsof.2012.08.008;  

### MR Information

#### MR1------Completely decompositing the brackets structure

Description:
Property: $[x_1\cdots x_n]$ or $[x_1-x_n] \Rightarrow [x_1|\cdots |x_n]$ where $[x_1\cdots x_n]$ or $[x_1-x_n]$ is a decomposition of the bracket,by using the symbol $|"$
Source input: $[abcdef]$ or $[a-f]$
Source output: $grep([abcdef]),grep([a-f])$
Follow-up input: $[a|b|c|d|e|f]$
Follow-up output: $grep([a|b|c|d|e|f])$
Input relation: $[abcdef]$ or $[a-f]$ is a decomposition of the bracket,by using the symbol $|"$
Output relation: $grep([abcdef])=grep([a|b|c|d|e|f]),grep([a-f])=grep([a|b|c|d|e|f])$
Pattern:

#### MR2------Splitting the brackets structure

Description:
Property: $[x_1,x_2,\cdots,x_{n-1},x_n] \Rightarrow ([x_1,x_2,\cdots]|[\cdots ,x_{n-1},x_n])$ where $([x_1,x_2,\cdots]|[\cdots ,x_{n-1},x_n])$ is split from $[x_1,x_2,\cdots,x_{n-1},x_n]$
Source input: $[abcdef]$ or $[a-f]$
Source output: $grep([abcdef])$ or $grep([a-f])$
Follow-up input: $([ab]|[c-f])$
Follow-up output: $grep([ab]|[c-f])$
Input relation: $([ab]|[c-f])$ is split from $([abcdef])$
Output relation: $[abcdef]=([ab]|[c-f])$ and $[a-f]=([ab]|[c-f])$
Pattern:

#### MR3------Bracketing simple characters

Description:
Property: $(x) \Rightarrow ([x])$ where simple character $(x)$ is equivalent to itself enclosed by the brackets $([x])$
Source input: $(abc)$
Source output:  $grep(abc)$
Follow-up input:  $([a][b][c])$
Follow-up output:  $grep([a][b][c])$
Input relation: simple character $(abc)$ is equivalent to itself enclosed by the brackets $([a][b][c])$
Output relation: $[abc]=([a][b][c])$
Pattern:
Insert title here