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.

  • $\begingroup$ You want two machine for op and pq? You mean any string that contains oppq? $\endgroup$
    – A. H.
    Jun 28, 2022 at 9:44
  • $\begingroup$ One machine that checks, that both op and pq are in the same string, could be opq, could be pqop, could be opoooopqqq, etc $\endgroup$
    – pguetschow
    Jun 28, 2022 at 9:52
  • $\begingroup$ Order is important? Mean op and then pq order should maintain? $\endgroup$
    – A. H.
    Jun 28, 2022 at 9:53
  • $\begingroup$ 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 $\endgroup$
    – pguetschow
    Jun 28, 2022 at 9:54
  • $\begingroup$ Do you able to design dfa from @Nathaniel answer? $\endgroup$
    – A. H.
    Jun 28, 2022 at 11:16

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.