SP15092 BFREGEX1 - A Kleene Implementation

Thor, the Norse god of thunder, was shopping for groceries when he noticed a sale on Kleenex brand tissues. This got him thinking about Kleene’s recursion theorem and its application to quines in functional programming languages. As this gave him a headache, he instead turned his attention to how one might recognise regular expressions with Kleene stars on a Turing machine. Unfortunately, this just made his headache worse. So he took out a slip of paper, jotted down a brainf\*\*k program to handle regular expressions containing Kleene plusses, paid for his groceries, and congratulated himself on a job well done. **Note:** You can use any programming language you want, as long as it is brainf\*\*k.

The first line contains an integer **T** (1 ≤ **T** ≤ 1000). Then follow **T** test cases. For each test case: The first line contains a regular expression **P** (1 ≤ |**P**| ≤ 30). The next line contains an integer **Q** (1 ≤ **Q** ≤ 10). Then follow **Q** lines, each containing a string **S** (1 ≤ |**S**| ≤ 100). Finally, there is an empty line at the end of each test case. Each line, including the last, is terminated by a single newline (linefeed) character, which has ASCII value 10. All regular expressions are guaranteed to be valid; in particular, **P** may not start with a plus, and it may not contain two consecutive plusses. **P** is a string over the alphabet {a,b,c,d,+}, and **S** is a string over the alphabet {a,b,c,d}.

**T** lines each containing a string of length **Q**. The **i**th character of the string indicates whether **S** is in the regular language defined by **P**: 'Y' for a match, and '.' otherwise. Note that we are concerned whether **P** matches **S**, as opposed to a substring of **S**. In other words, we could insert '^' at the beginning of **P** and '$' at the end, and then test for a match using e.g. m// in Perl. See the example for further clarification.