Simulate the classic two-state DFA.
What to build
A program that runs the DFA for "an even number of a's" on several words.
Requirements
- Use two states and a transition table, not str.count.
- Print
acceptorrejectfor each word, in order.
Input
Line 1: n. Then n lines, each a word over {a, b} (a line may be empty, meaning ε).
Output
n lines, each accept or reject.
Constraints
1 ≤ n ≤ 20; each word has at most 40 symbols.
Example
Input:
3
ab
aab
bbb
Output:
reject
accept
accept
Why it works
The DFA only needs to remember whether it has seen an even or odd number of a's, and b leaves that unchanged.
Examples
Example 1 · Input
3 ab aab bbb
Expected output
reject accept accept
Example 2 · Input
2 aaaa a
Expected output
accept reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Two states are enough: one for "even so far" and one for "odd so far".
Hint 2
Read n first, then call input() n times; a word may be an empty line.
Solution
Show one correct solution (try it yourself first)
delta = {("E", "a"): "O", ("E", "b"): "E", ("O", "a"): "E", ("O", "b"): "O"}
n = int(input())
for _ in range(n):
state = "E"
for symbol in input():
state = delta[(state, symbol)]
print("accept" if state == "E" else "reject")