How can I continue to find a regular expression?

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Expression Regular
Click For Summary

Discussion Overview

The discussion revolves around the regularity of the language $\{0^{m}1^{n}:m+n \geq 2\}$ over the alphabet $\Sigma=\{0,1\}$. Participants explore how to derive a regular expression that represents this language, examining specific cases and the implications of their proposed expressions.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants propose that the regular expression could be formed by concatenating an arbitrary number of zeroes to the left and an arbitrary number of ones to the right of the words $00$, $01$, and $11$.
  • A proposed regular expression is $\{0^{*} \cdot 00 \cdot 1^{*}|0^{*} \cdot 01 \cdot 1^{*}|0^{*} \cdot 11 \cdot 1^{*}\}$, which some participants believe should be verified against the language's criteria.
  • Participants question whether all words generated by the proposed regular expression are indeed part of the language and whether all words in the language can be generated by the expression.
  • There is a discussion about specific cases, such as when $m=0$, $m=1$, and $m \geq 2$, to evaluate the correctness of the proposed regular expression.
  • Some participants express uncertainty about the correctness of their reasoning, particularly regarding the inclusion of words formed solely by $1$s.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the correctness of the proposed regular expression. While some express confidence in its validity, others remain uncertain and seek further verification.

Contextual Notes

Participants highlight the need to ensure that the proposed regular expression captures all words in the language and that all words generated by the expression belong to the language, indicating potential limitations in their current understanding.

Who May Find This Useful

Readers interested in formal language theory, regular expressions, and the properties of languages over finite alphabets may find this discussion relevant.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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:
 
Technology news on Phys.org
Re: How can I continue?

evinda said:
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?
 
Re: How can I continue?

I like Serena said:
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^{*}\}$$
?
 
Re: How can I continue?

evinda said:
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?
 
Re: How can I continue?

I like Serena said:
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:

I like Serena said:
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:
 
Re: How can I continue?

evinda said:
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
 
Re: How can I continue?

I like Serena said:
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?
 
Re: How can I continue?

evinda said:
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)
 
Re: How can I continue?

I like Serena said:
Yep! (Whew)

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

Similar threads

MHB Regularity of a Language without the Letter S Repeated n Times
  • · Replies 15 ·
Replies
15
Views
3K
Undergrad How to Express Non-regular Prior Distributions by Mathematical Formula
  • · Replies 2 ·
Replies
2
Views
2K
MHB Regular Expressions Help: Find Language for DFA Drawing
  • · Replies 13 ·
Replies
13
Views
4K
MHB How can I check if the grammar is regular?
  • · Replies 10 ·
Replies
10
Views
7K
How many words of length n are there in this regular language?
  • · Replies 1 ·
Replies
1
Views
2K
Python How Can I Correct My Python Regular Expressions Code for Analyzing Swallow Data?
  • · Replies 1 ·
Replies
1
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
MHB Convert an automaton into a regular expression
  • · Replies 1 ·
Replies
1
Views
2K
How Can We Efficiently Parallelize the N-Queens Problem?
  • · Replies 11 ·
Replies
11
Views
4K
MHB Context-Free Langs: S-L Check if Not CF?
  • · Replies 15 ·
Replies
15
Views
4K