Play the prover's side of the pumping game by search.
What to build
A program that finds the first word of a language that no allowed split can pump, or reports that there is none in range.
Requirements
- Support
anbn,equal(as many a's as b's),abstar((ab)*) andeven(even length), over {a, b}. - Print
w=WORDfor the first witness of length p to 2p + 2, ornone up to length Lwith L = 2p + 2.
Input
Line 1: the language name. Line 2: p.
Output
One line.
Constraints
1 ≤ p ≤ 4.
Example
Input:
anbn
2
Output:
w=ab
Why it works
For a non-regular language there are words no split can pump; for a regular language every long enough word has a surviving split, so no witness is found.
Examples
Example 1 · Input
anbn 2
Expected output
w=ab
Example 2 · Input
even 2
Expected output
none up to length 6
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Search words of L by length from p to 2p + 2, and within a length in product("ab", ...) order.
Hint 2
A word is a witness when every split with |xy| ≤ p and |y| ≥ 1 fails for some k in 0 to 3.
Solution
Show one correct solution (try it yourself first)
import re
from itertools import product
name = input()
p = int(input())
def anbn(s):
n = len(s) // 2
return s == "a" * n + "b" * n
languages = {
"anbn": anbn,
"equal": lambda s: s.count("a") == s.count("b"),
"abstar": lambda s: re.fullmatch("(ab)*", s) is not None,
"even": lambda s: len(s) % 2 == 0,
}
language = languages[name]
def witness():
for length in range(p, 2 * p + 3):
for letters in product("ab", repeat=length):
w = "".join(letters)
if not language(w):
continue
survives = False
for i in range(p):
for j in range(i + 1, p + 1):
x, y, z = w[:i], w[i:j], w[j:]
if all(language(x + y * k + z) for k in range(4)):
survives = True
if not survives:
return w
return None
w = witness()
print(f"w={w}" if w else f"none up to length {2 * p + 2}")