1
$\begingroup$

Write a regular expression for the language of words over $\{0,1,2\}$ satisfying the following requirements:

  • The word has length at least 3.
  • The last symbol is 2.
  • The second to last symbol isn't 0.
  • The combination of the last two symbols doesn’t appear anywhere else in the string.
$\endgroup$

closed as unclear what you're asking by Evil, Discrete lizard Sep 30 at 6:16

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ It's really better if you solved this on your own. $\endgroup$ – Yuval Filmus Sep 28 at 22:28
  • $\begingroup$ Yeah I know..I have been trying the last 3 hours but I am really stuck.I could use some guidance at least $\endgroup$ – stathis korakas Sep 28 at 22:36
  • $\begingroup$ Perhaps you could show us what you did manage to do. $\endgroup$ – Yuval Filmus Sep 28 at 22:37
  • $\begingroup$ (0+1+2)[(10*+11*+2*)]*(12*) I wrote this for the case where the second to last symbol is 1 but it doesn’t seem right at all $\endgroup$ – stathis korakas Sep 28 at 22:50
1
$\begingroup$

In order to solve this exercise, we need to come up for regular expressions for two classes of words:

  • Words of the form $x00$, where $x \neq \epsilon$ and the only occurrence of $00$ is at the end.
  • Words of the form $x01$, where $x \neq \epsilon$ and the only occurrence of $01$ is at the end.

Let us start with the first class. For starters, $x$ must end with $1$ or $2$. So such words are of one of the forms $y100$ or $y200$, where $y$ doesn't contain $00$. Presumably you already know how to describe all words not containing $00$ using a regular expression.

For the second class, the only constraints on $x$ are that it is non-empty and doesn't contain $01$. If you don't like the "non-empty" constraint, you can use the following case distinction:

  • If $x = y0$ or $x = y2$, then the only constraint on $y$ is that it doesn't contain $01$.
  • If $x = y1$, then $y$ cannot end with $0$. It could be empty. If it ends with $2$, then $x$ is of the form $z21$. If it ends with $1$, then we're again in the same situation: the preceding symbol (if any) cannot be $0$. Continuing in this way, we see that either $x \in 1^+$ or $x$ is of the form $y2z$, where $y$ doesn't contain $01$ and $z = 1^n$ for some $n \geq 1$.

I'll let you figure out how to describe strings $y$ avoiding $01$ – this is very similar to the case of avoiding $00$.

$\endgroup$
  • $\begingroup$ Thank you so much for your time.One more question..do you think by drawning the DFA would help me to answer the problem because I tried it and I got even more confused $\endgroup$ – stathis korakas Sep 28 at 23:23
  • $\begingroup$ I'm not sure it would be too helpful, since regular expressions are quite different from DFAs. However, there is an algorithm that converts a DFA to an equivalent regular expression. $\endgroup$ – Yuval Filmus Sep 28 at 23:33
  • $\begingroup$ Alright I’ll keep that in mind. $\endgroup$ – stathis korakas Sep 28 at 23:36

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