I'm currently working through some regular expression questions and I've got a solution for one of the problems that I'm not certain is correct.

The question has this preface.

We only consider languages over the alphabet $\{0, 1, 2\}$.

We also view words over this alphabet as ternary numbers. For the language below give either a regular expression that describes it or a proof that the language is not regular. Note that e.g. the set of integers $\{4, 7, 11\}$ (in decimal notation) becomes in this view the language $\{11, 21,102\}$.

The question - The set of all words that contain more 1s than 2s.

Would the regular expression (11)2 suffice for this?

  • 5
    $\begingroup$ That regular expressions seems to recognise only one single word. At the very least, you must recognise 112222111 and not recognise 11222211. I'd try the "proof that the language is not regular" myself. $\endgroup$ – gnasher729 Oct 25 '16 at 13:45
  • 3
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Oct 25 '16 at 14:14

No. The regular expression $(11)2$ describes the language $\{ 112 \}$, which is clearly not the language of all strings with this property.

Hint: Can you really count character occurrences using the regular operators?

| cite | improve this answer | |

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