Theory: Two DFAs at once

Use the product construction to answer an intersection and a union in one pass.

What to build

A program that reads two complete DFAs and reports, for each word, whether it is in L1 ∩ L2 and in L1 ∪ L2.

Requirements

  • Read each word once, moving both machines together.
  • Print and accept|reject or accept|reject for each word.

Input

DFA 1, then DFA 2, each as: start, accepting states, t, t lines from symbol to. Then n and n words (a word may be an empty line).

Output

n lines, such as and reject or accept.

Constraints

Each DFA has at most 10 states and is complete; at most 20 words.

Example

Input:

E
E
4
E a O
E b E
O a E
O b O
s
f
6
s a A
s b s
A a A
A b f
f a f
f b f
3
aab
ab
bb

Output:

and accept or accept
and reject or accept
and reject or accept

Why it works

A pair of states is a state of the product DFA; accepting pairs for "and" and "or" give intersection and union.

Examples

Example 1 · Input
E
E
4
E a O
E b E
O a E
O b O
s
f
6
s a A
s b s
A a A
A b f
f a f
f b f
3
aab
ab
bb
Expected output
and accept or accept
and reject or accept
and reject or accept
Example 2 · Input
N
Y
4
N a N
N b Y
Y a N
Y b Y
E
E
4
E a O
E b E
O a E
O b O
3
a

aab
Expected output
and reject or reject
and reject or accept
and accept or accept

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

Hints

Hint 1

Run both DFAs in step: keep a pair (state1, state2) and move both halves on each symbol.

Hint 2

"and" accepts when both halves accept; "or" when at least one does.

Solution

Show one correct solution (try it yourself first)
def read_dfa():
    start = input().strip()
    accepting = set(input().split())
    delta = {}
    for _ in range(int(input())):
        a, symbol, b = input().split()
        delta[(a, symbol)] = b
    return start, accepting, delta


s1, f1, d1 = read_dfa()
s2, f2, d2 = read_dfa()
for _ in range(int(input())):
    p, q = s1, s2
    for c in input():
        p, q = d1[(p, c)], d2[(q, c)]
    both = p in f1 and q in f2
    either = p in f1 or q in f2
    print("and", "accept" if both else "reject", "or", "accept" if either else "reject")

Lesson: Designing DFAs: memory, complement and product →