Help with Regular Expression

92 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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?