Apply grammar rules one at a time and print each step.
What to build
A program that applies a list of rules, each to the leftmost variable, and prints the sentential form after each step.
Requirements
- Print the start variable first, then the form after each rule.
- The token ε as a body means the empty string; print ε when the form is empty.
Input
Line 1: the start variable. Line 2: n. Then n rules A -> body; each rule's A is the leftmost variable at that point.
Output
n + 1 lines.
Constraints
n ≤ 10; forms stay under 40 symbols.
Example
Input:
S
3
S -> aSb
S -> aSb
S -> ε
Output:
S
aSb
aaSbb
aabb
Why it works
A leftmost derivation always rewrites the leftmost variable, so the steps are fixed by the list of rules.
Examples
Example 1 · Input
S 3 S -> aSb S -> aSb S -> ε
Expected output
S aSb aaSbb aabb
Example 2 · Input
S 2 S -> AB A -> a
Expected output
S AB aB
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Variables are capital letters; find the leftmost one with a loop or next(...).
Hint 2
Replace only that one occurrence: form[:i] + body + form[i + 1:].
Solution
Show one correct solution (try it yourself first)
form = input().strip()
print(form)
for _ in range(int(input())):
head, body = input().split(" -> ")
body = "" if body == "ε" else body
i = next(k for k, c in enumerate(form) if c.isupper())
form = form[:i] + body + form[i + 1:]
print(form or "ε")