Theory: Find a word that cannot be pumped

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)*) and even (even length), over {a, b}.
  • Print w=WORD for the first witness of length p to 2p + 2, or none up to length L with 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}")

Lesson: Beyond regular: the pumping lemma →