MHB How can I continue to find a regular expression?

[evinda]

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?

 

[I like Serena]

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?

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]

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^{*}\}$$
?

 

[I like Serena]

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]

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?

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??

 

[I like Serena]

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?
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??

Without the sentences it is all correct. :p

 

[evinda]

Re: How can I continue?

Without the 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?

 

[I like Serena]

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]

Re: How can I continue?

Yep! (Whew)

Nice!Thank you very much for your help! :)