Welcome to our community

Be a part of something great, join today!

How can I continue to find a regular expression?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Hello!!! :)
I have a question:
Suppose that $\Sigma=\{0,1\}$.Is the language $\{0^{m}1^{n}:m+n \geq 2\}$ regular?
I tried to find a regular expression.I checked the case $m+n=2$ and I found that the possible words are $00,01,11$ .But..how can I continue? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,776
Re: How can I continue?

Hello!!! :)
I have a question:
Suppose that $\Sigma=\{0,1\}$.Is the language $\{0^{m}1^{n}:m+n \geq 2\}$ regular?
I tried to find a regular expression.I checked the case $m+n=2$ and I found that the possible words are $00,01,11$ .But..how can I continue? :confused:
Perhaps you can concatenate an arbitrary number of zeroes to the left side of each of those possible words?
And also concatenate an arbitrary number of ones on the right side?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Re: How can I continue?

Perhaps you can concatenate an arbitrary number of zeroes to the left side of each of those possible words?
And also concatenate an arbitrary number of ones on the right side?
So,you mean that the regular expression is
$$ \{0^{*} \cdot 00 \cdot 1^{*}|0^{*} \cdot 01 \cdot 1^{*}|0^{*} \cdot 11 \cdot 1^{*}\}$$
?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,776
Re: How can I continue?

So,you mean that the regular expression is
$$ \{0^{*} \cdot 00 \cdot 1^{*}|0^{*} \cdot 01 \cdot 1^{*}|0^{*} \cdot 11 \cdot 1^{*}\}$$
?
We'll have to verify! (Wondering)
All words in the regular expression should be contained in the language, and conversely all words in the language should match with the regular expression.

Are all words formed by the regular expression part of the language?

For the other direction, suppose we pick m=0, that is, no zeroes, are all words with only $1$'s matched by the regular expression?
How about m=1, m=2, and m>2?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Re: How can I continue?

We'll have to verify! (Wondering)
All words in the regular expression should be contained in the language, and conversely all words in the language should match with the regular expression.

Are all words formed by the regular expression part of the language?
Since,each word has at least 2 symbols and the sequence of $0$ precedes the sequence of $1$,all words formed by the regular expression are part of the language.Or am I wrong? :confused:

For the other direction, suppose we pick m=0, that is, no zeroes, are all words with only $1$'s matched by the regular expression?
How about m=1, m=2, and m>2?
When $m=0$,we get a sequence only of $1$'s,from $0^{*} \cdot 11 \cdot 1^{*}$,for $m=1$ we get a word from $0^{*} \cdot 01 \cdot 1^{*}$ or from $0^{*} \cdot 11 \cdot 1^{*}$, for $m \geq 2$ we get a word from $0^{*} \cdot 00 \cdot 1^{*} $ or from $0^{*} \cdot 01 \cdot 1^{*}$ or from $0^{*} \cdot 11 \cdot 1^{*}$ .

So,the expression is correct?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,776
Re: How can I continue?

Since,each word has at least 2 symbols and the sequence of $0$ precedes the sequence of $1$,all words formed by the regular expression are part of the language.Or am I wrong? :confused:



When $m=0$,we get a sequence only of $1$'s,from $0^{*} \cdot 11 \cdot 1^{*}$,for $m=1$ we get a word from $0^{*} \cdot 01 \cdot 1^{*}$ or from $0^{*} \cdot 11 \cdot 1^{*}$, for $m \geq 2$ we get a word from $0^{*} \cdot 00 \cdot 1^{*} $ or from $0^{*} \cdot 01 \cdot 1^{*}$ or from $0^{*} \cdot 11 \cdot 1^{*}$ .

So,the expression is correct?? :confused:
Without the :confused: sentences it is all correct. :p
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Re: How can I continue?

Without the :confused: sentences it is all correct. :p
Great!!! ;)

So,could I write it like that?
The possible words with length 2 are $00,01,11$.
To have words with length greater than 2,we concatenate an arbitrary number of zeroes to the left side of each of those possible words and an arbitrary number of ones on the right side.So,the expression is $\{0^{*} \cdot 00 \cdot 1^{*}|0^{*} \cdot 01 \cdot 1^{*}| 0^{*}\cdot 11 \cdot 1^{*} \}$ and then I will show that it is valid?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,776
Re: How can I continue?

Great!!! ;)

So,could I write it like that?
The possible words with length 2 are $00,01,11$.
To have words with length greater than 2,we concatenate an arbitrary number of zeroes to the left side of each of those possible words and an arbitrary number of ones on the right side.So,the expression is $\{0^{*} \cdot 00 \cdot 1^{*}|0^{*} \cdot 01 \cdot 1^{*}| 0^{*}\cdot 11 \cdot 1^{*} \}$ and then I will show that it is valid?
Yep!! (Whew)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720