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
S 1 S -> aSb | ε 6
ε ab aabb aaabbb count 4
S 1 S -> (S)S | ε 4
ε () (()) ()() 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))