Theory: All short strings of a grammar

List the language of a grammar up to a length.

What to build

A program that prints every string of length at most L that a grammar generates.

Requirements

  • Print the strings sorted by length, then alphabetically; print ε for the empty string.
  • Finish with count N.

Input

Line 1: the start variable. Line 2: r. Then r lines A -> body | body | ... (ε is the empty body). Last line: L.

Output

The strings, then count N.

Constraints

Variables are capital letters; every other symbol is a terminal. L ≤ 6.

Example

Input:

S
1
S -> aSb | ε
6

Output:

ε
ab
aabb
aaabbb
count 4

Why it works

Every string in the language comes from expanding variables; bounding the terminals makes the search finite.

Examples

Example 1 · Input
S
1
S -> aSb | ε
6
Expected output
ε
ab
aabb
aaabbb
count 4
Example 2 · Input
S
1
S -> (S)S | ε
4
Expected output
ε
()
(())
()()
count 4

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

Hints

Hint 1

Keep a stack of forms (tuples of symbols) and always expand the leftmost variable in every way.

Hint 2

Skip forms with more than L terminals or longer than 2L + 2 symbols, and remember the forms you have seen.

Solution

Show one correct solution (try it yourself first)
start = input().strip()
grammar = {}
for _ in range(int(input())):
    head, bodies = input().split(" -> ")
    for body in bodies.split(" | "):
        grammar.setdefault(head, []).append(() if body == "ε" else tuple(body))
L = int(input())
found, seen = set(), set()
todo = [(start,)]
while todo:
    form = todo.pop()
    terminals = [s for s in form if s not in grammar]
    if form in seen or len(terminals) > L or len(form) > 2 * L + 2:
        continue
    seen.add(form)
    i = next((k for k, s in enumerate(form) if s in grammar), None)
    if i is None:
        found.add("".join(form))
        continue
    for body in grammar[form[i]]:
        todo.append(form[:i] + body + form[i + 1:])
words = sorted(found, key=lambda w: (len(w), w))
for w in words:
    print(w or "ε")
print("count", len(words))

Lesson: Context-free grammars →