Theory: List a regular language

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)

Lesson: Regular expressions →