Print the regex pattern where the string becomes invalid

Question

Given the regular expression

^(aa|bb){1}(a*)(ab){1}$

For the language,

All strings starting with double letters and ends with substring ab

I would like to know if it is possible to print the regex code where the string becomes invalid. This has got to do with regular expressions in Finite Automata.

For example i have these following input set of invalid strings,

abaa
aabb
aaba

I wanted to have an output like this,

abaa ^(aa|bb){1}
aabb ^(aa|bb){1}(a*)
aaba ^(aa|bb){1}(a*)(ab){1}$

Answer 1

You can create a Regex from a string, if it is a malformed pattern it is going to throw an exception. You can create a loop that's going to get substring of the pattern an try to create a regex, if it fails just continue.

Once you have a Regex you can test for a match and store the last pattern that matched the input. So it would be something like this:

public static string FindBestValidRegex(string input, string pattern)
{
    var lastMatch = "";

    for (int i = 0; i < pattern.Length; i++)
    {
        try
        {
            var partialPattern = pattern.Substring(0, i + 1);
            var regex = new Regex(partialPattern);

            if (regex.IsMatch(input))
            {
                lastMatch = partialPattern;
            }
        }
        catch { }
    }

    return lastMatch;
}

Testing:

static void Main(string[] args)
{
    var pattern = @"^(aa|bb){1}(a*)(ab){1}$";

    Console.WriteLine(FindBestValidRegex("bbb", pattern));
    Console.WriteLine(FindBestValidRegex("aabb", pattern));
    Console.WriteLine(FindBestValidRegex("aaab", pattern));
    Console.WriteLine(FindBestValidRegex("bbaab", pattern));

    Console.ReadKey();
}

Output:

^(aa|bb){1}(a*)
^(aa|bb){1}(a*)
^(aa|bb){1}(a*)(ab){1}$
^(aa|bb){1}(a*)(ab){1}$