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) andabstar((ab)*). - Print
splits Nand thensurvive 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)