.NET Fiddle

CSharp · Console

/Program.cs

using System;
using System.Text.RegularExpressions;

public class Example
{
    public static void Main()
    {
        string pattern = @"(?<statement>(?<word>\w+)+\s+(With|Without)\s+(?<-word>\w+)+(?(word)(?!)))|(?<statement>\sAND\s)|(?<remainder>\sAND$)";
        string input = @" Tom With Jane AND Mike Without Anne AND";
        
        foreach (Match m in Regex.Matches(input, pattern))
        {
            Console.WriteLine("'{0}' found at index {1}.", m.Value, m.Index);
        }
    }
}