# Language over $\{0,1\}$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every word is of length $n$ or greater (with $n \in \mathbb{N}$ and fixed, say $n=5$) AND every word contains at least two $1$'s?

-
You just did describe it. Are you perhaps wondering how to describe it in terms of a regular expression or a regular grammar? –  Brian M. Scott Nov 17 '12 at 11:47
I would like to know how to describe it using operations. Like $\{00, 11, 01, 10\}^*$ describes the language over $\{0,1\}$ that consists of all even-length strings. –  Toby Nov 17 '12 at 12:12
That’s not really using operations: that’s simply listing them. The language of words of length at most $5$ containing at least two $1$’s is a lot bigger; are you sure that you just want to list its members? –  Brian M. Scott Nov 17 '12 at 12:15
It sure is an operation, namely the kleene star operation. –  Toby Nov 17 '12 at 12:18
Ah, yes: I didn’t notice the star before; was it perhaps at midline instead of an exponent? Anyway, now I know what you want: you want a regular expression. Unfortunately, that’s going to amount very nearly to listing the words, on account of the length limitation; you won’t get any very significant compression. –  Brian M. Scott Nov 17 '12 at 12:20

You can do this directly (without any regex theory) by splitting it into cases:

_1_1_00000000000    a short string with two 1s then zeros
_1___...1.......    a short string with one 1 then a long string with at least one 1
00000...1...1...    a short string of zeros then a long string with two 1's


Let $R$ be the regex for a short string with two 1s and $R'$ for a short string with one 1 (which we already know how to produce) then $$R0^* + R'(0+1)^*1(0+1)^* + 00000(0+1)^*1(0+1)^*1(0+1)^*$$ matches strings with length at least 5 containing at least two 1's.

(note: if you simplified the regex produced by the differentiation method you wouldn't get a regex quite as simple as this, because I we coded into this one the string of zeros fact in the first and last cases)

-

The typical approach is to write out a string that says: "Any number of 0's and 1's" then 1 then "any number of 0's and 1's" then 1 then "any number of 0's and 1's". This will get you all strings that have at least two 1's, but it allows strings as short as length 2 (ie, the "11" string). But you also have a minimum length requirement.

To get this length requirement enforced alongside the "two 1's" required is tricky and the ugliness of expressing it depends on your rules of what's allowed in expressing the language. The easiest way is $$\{0,1\}^{\geq n} - 0^* - 0^*10^*$$ which is just saying "all strings of length at least $n$ except those that are only 0's or only have one 1." Since each of the terms above is a regular language, and since regular languages are closed under set difference, the expression above is a regular language and it is easily seen to give the result you desire.

-

This is trivial because the language is finite. Just list all the strings.

-
Thank you for helping, but I made a mistake indeed... it should be: strings of length $\ge n$ –  Toby Nov 17 '12 at 14:22

We want to create a regex which matches all strings of length 5 or greater with at least two 1's. A good start is that the regex $$R = (0+1)^*1(0+1)^*1(0+1)^*$$ will match all strings with at least two 1s in it.

To turn this into a regex who matches all strings of a length $\ge 5$ (say) we could differentiate it 5 times and delete the terminal symbols in this prefix.

Recall that differentiation $D_a$ of a regex with respect to a symbol $a$ produces a new regex matching $s$ whenever the original matched $as$. In this way we create a new regex $R_1 = (0 + D_0 R)(1 + D_1 R)$ which matches strings of length at least 1 (actually it will always match strings with length $\ge 2$ but for uniformity we say at least 1), then $R_2 = (0 + D_0 R_1)(1 + D_1 R_1)$ matches strings of length at least 2 etc..

-