Search for a string that tells two regular expressions apart.
What to build
A program that compares two expressions on every string over {a, b} up to length k.
Requirements
- If they agree on all of them, print
same up to k. - Otherwise print the first string where they differ, shortest first in product order, as
differ on W: first yes|no, second yes|no(ε for the empty string).
Input
Line 1: the first expression. Line 2: the second. Line 3: k.
Output
One line.
Constraints
0 ≤ k ≤ 8.
Example
Input:
(a|b)*
(a*b*)*
5
Output:
same up to 5
Why it works
Two expressions describe different languages exactly when some string is in one and not the other; the shortest such string is found first.
Examples
Example 1 · Input
(a|b)* (a*b*)* 5
Expected output
same up to 5
Example 2 · Input
a*b* (ab)* 3
Expected output
differ on a: first yes, second no
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Try every string over {a, b} up to length k, shortest first, and compare the two fullmatch answers.
Hint 2
Stop at the first string where they disagree.
Solution
Show one correct solution (try it yourself first)
import re
from itertools import product
first = input()
second = input()
k = int(input())
def find():
for length in range(k + 1):
for letters in product("ab", repeat=length):
w = "".join(letters)
x = bool(re.fullmatch(first, w))
y = bool(re.fullmatch(second, w))
if x != y:
return w, x, y
return None
found = find()
if found:
w, x, y = found
print(f"differ on {w or 'ε'}: first {'yes' if x else 'no'}, second {'yes' if y else 'no'}")
else:
print("same up to", k)