Theory: An even number of a's

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 accept or reject for 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")

Lesson: Deterministic finite automata (DFA) →