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