Theory: Which splits survive?

Count the splits that the pumping lemma allows, and the ones that survive pumping.

What to build

A program that counts, for a word of a given language, all splits with |xy| ≤ p and |y| ≥ 1, and how many survive pumping.

Requirements

  • Support the languages anbn (aⁿbⁿ), even (even length) and abstar ((ab)*).
  • Print splits N and then survive M.

Input

Line 1: the language name. Line 2: p. Line 3: a word w of that language with |w| ≥ p.

Output

Two lines.

Constraints

1 ≤ p ≤ 8; |w| ≤ 20.

Example

Input:

anbn
3
aaabbb

Output:

splits 6
survive 0

Why it works

For a regular language some split always survives when p is large enough; for aⁿbⁿ none does, which is the heart of the proof.

Examples

Example 1 · Input
anbn
3
aaabbb
Expected output
splits 6
survive 0
Example 2 · Input
even
2
abab
Expected output
splits 3
survive 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Try every 0 ≤ i < j ≤ p with x = w[:i], y = w[i:j], z = w[j:].

Hint 2

A split survives when x + y * k + z is in the language for k = 0, 1, 2 and 3.

Solution

Show one correct solution (try it yourself first)
import re

name = input()
p = int(input())
w = input()


def anbn(s):
    n = len(s) // 2
    return s == "a" * n + "b" * n


languages = {
    "anbn": anbn,
    "even": lambda s: len(s) % 2 == 0,
    "abstar": lambda s: re.fullmatch("(ab)*", s) is not None,
}
language = languages[name]
splits = survive = 0
for i in range(p):
    for j in range(i + 1, p + 1):
        splits += 1
        x, y, z = w[:i], w[i:j], w[j:]
        if all(language(x + y * k + z) for k in range(4)):
            survive += 1
print("splits", splits)
print("survive", survive)

Lesson: Beyond regular: the pumping lemma →