Hier mal eine lustige Aufgabe, mit der ich vor Kurzem konfrontiert war: Gegeben sei ein Alphabet Σ mit Symbolen und eine Regular Expression, wie etwa (0*|1*)(0*|1*)(0*|1*). Nun ist dar kürzeste String mit Symbolen aus dem Alphabet gesucht, auf dass der gegebene RegExp nicht passt.
…Hier würde etwas Musik gespielt und ein Countdown eingeblendet werden, damit der interessierte Leser eine Lösung erarbeiten kann 🙂 …
Meine Lösung funktioniert, sofern die Symbole im Alphabet einem Symbol in UTF-8 entsprechen und ist trivial: Zuerst werden alle Permutationen gebildet und der RegExp daran getestet. Aus reinem Masochismus habe ich versucht, dies in Python 3.2 zu implementieren. Und nein, itertools packt das nicht!
Ein Testdurchgang könnte folgendermassen aussehen (Das Alphabet besteht aus 0 und 1):
$ python3.2 msfr.py -v '(0*|1*)(0*|1*)(0*|1*)' 0 1
Σ: {0, 1}
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with ε MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 00 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0011 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0100 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0101 NOMATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0110 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1010 NOMATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1011 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1111 MATCH
Found nonmatching strings with length 4: 0101, 1010
Klappt also nicht schlecht. ε ist übrigens der leere String :).
Dies ist mein erstes Script in Python überhaupt. Für Anregungen und Verbesserungsvorschläge bin ich mehr als dankbar:
'''
Find a minimal non-matching string for a given regular expression and an alphabet.
Created on Oct 1, 2011
@author: Skaldrom Y. Sarg
'''
import argparse
import re
import sys
def allstrings(alphabet, length):
"""Find the list of all strings of 'alphabet' of length 'length'"""
if length == 0:
return [""]
c = []
for i in range(length): # @UnusedVariable
c = [[x] + y for x in alphabet for y in c or [[]]]
return c
if __name__ == '__main__':
scriptHelp= "msfr: Find a minimal non-matching string for a given regular expression and an alphabet.\n\
\n\
Example: python3 msfr.py '(0*|1*)(0*|1*)(0*|1*)' 0 1"
parser = argparse.ArgumentParser(description=scriptHelp, epilog='Written by Michael Schneider.')
parser.add_argument('-v, --verbose', dest='verbose', action='store_true', default=False, help='output more verbose')
parser.add_argument('-m, --maxlength', dest='maxlength', default=10, help='max number of symbols to test (default: 10)')
parser.add_argument('regexp', type=str, nargs=1, help='the regular expression')
parser.add_argument('alphabet', metavar='S', type=str, nargs='+', help='a symbol of the alphabet')
args = parser.parse_args()
# Start
if(args.verbose):
print('Σ: {' + ", ".join(args.alphabet)+'}')
foundNonMatch = []
for wordlength in range(0, args.maxlength):
for string in allstrings(args.alphabet, wordlength):
testString = "".join(string)
testRegexp = args.regexp[0]
if args.verbose:
print(" Testing: '^" + testRegexp + "$' with " + (testString if len(testString) != 0 else 'ε'), end="")
try:
result = re.match('^' + testRegexp + '$', testString)
except re.error as exc:
if args.verbose:
print("\n")
print("ERROR - Invalid regexp: " + str(exc))
sys.exit(0)
if(result != None):
if args.verbose:
print(" MATCH")
else:
foundNonMatch.append(testString)
if args.verbose:
print(" NOMATCH")
if(foundNonMatch):
break
if not foundNonMatch:
print("No nonmatching strings found until length " + args.maxlength + ".")
else:
foundStingsLength = str(len(foundNonMatch[0]))
foundStrings = ", ".join(foundNonMatch) if len(foundNonMatch[0]) > 0 else 'ε'
print("Found nonmatching string" + ("s" if len(foundNonMatch) else "") + " with length " + foundStingsLength +": " +foundStrings)