How would you write a regular expression that matches exactly the strings over the alphabet {A, . . . , Z} that contains the letter "O" only if they contain the letter "I" and contain at most two "E"’s.

  • $\begingroup$ Is a string with a letter "I" and at most two "E"'s without on "O" valid? $\endgroup$ – Q the Platypus Nov 25 '19 at 4:20
  • $\begingroup$ Yes it would be valid $\endgroup$ – Vig E Oh Nov 25 '19 at 4:30

Hint. As observed by @q-the-platypus, your condition is ambiguous. Here I will interpret it as the set of words

(that contains the letter "O" only if it contains the letter "I") and (contains at most two "E"’s).

The first part means that

if it contains "O", then it contains "I"

or, equivalently, since $p \rightarrow q$ is logically equivalent to "$q$ or not $p$",

either it contains "I" or it does not contain "O".

Thus your language is the union of the languages $L_1$ and $L_2$, where \begin{align} L_1 &= \{ \text{words containing "I" and at most two "E"'s}) \\ L_2 &= \{ \text{words containing no "O" and at most two "E"'s}) \end{align} Can you finish the exercise now?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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