Cheap and Secure Web Hosting Provider : See Now

[Solved]: The set of all words containing more 1's than 2s

, , No Comments
Problem Detail: 

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?

Asked By : K.Lonovan

Answered By : Hans Hüttel

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65099

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback