# DFA and NFA with 2 Substrings

I am preparing for my CS exam and found this question in a collection of old exams:

Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string.

I thought, I understood this topic, but I can not find a regular expression for this problem.

My initial thought was {o ∪ p ∪ q ∪ op+ ∩ pq+}* but that seems wrong to me. Can anyone give me a clue or answer, so I can understand this and develop the automatons by myself?

Another idea was {o ∪ p ∪ q}* {opq ∪ pqop}+ {o ∪ p ∪ q}*, but that seems too 'hard coded' for me.

• You want two machine for op and pq? You mean any string that contains oppq? Jun 28, 2022 at 9:44
• One machine that checks, that both op and pq are in the same string, could be opq, could be pqop, could be opoooopqqq, etc Jun 28, 2022 at 9:52
• Order is important? Mean op and then pq order should maintain? Jun 28, 2022 at 9:53
• No, the order is irrelevant, as far as I understand this question. One substring or in order would be easy, but I am struggling with this one Jun 28, 2022 at 9:54
• Do you able to design dfa from @Nathaniel answer? Jun 28, 2022 at 11:16

Find an automaton for $$L_1= \{uopv\mid u,v\in \Sigma^*\}$$ and an automaton for $$L_2 = \{upqv\mid u,v\in\Sigma^*\}$$ (this should be easy enough).
Then, you can compute the product automaton of the two languages, accepting $$L_1\cap L_2$$.