See a language by listing its shortest strings.
What to build
A program that lists every string over {a, b} of length up to k that an expression describes.
Requirements
- List strings by length, and within a length in the order product("ab", ...) gives.
- Print ε for the empty string and finish with
count N.
Input
Line 1: the expression. Line 2: k.
Output
The strings, one per line, then count N.
Constraints
0 ≤ k ≤ 5.
Example
Input:
(ab)*
4
Output:
ε
ab
abab
count 3
Why it works
Enumerating Σ* by length and filtering with the expression shows exactly which short strings belong to its language.
Examples
Example 1 · Input
(ab)* 4
Expected output
ε ab abab count 3
Example 2 · Input
a*b 2
Expected output
b ab count 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Generate strings shortest first with itertools.product("ab", repeat=length).
Hint 2
Keep the ones re.fullmatch accepts, and print ε for the empty string.
Solution
Show one correct solution (try it yourself first)
import re
from itertools import product
pattern = input()
k = int(input())
count = 0
for length in range(k + 1):
for letters in product("ab", repeat=length):
word = "".join(letters)
if re.fullmatch(pattern, word):
print(word or "ε")
count += 1
print("count", count)