Welcome to our community

Be a part of something great, join today!

regular expressions!

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Hello!!!
I have to draw the DFA of the language of the following expressions:
a){[tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex]}
b)[tex](\{\{1,0\}^{*},(\varnothing,2)^*\})^{*}[/tex]

Could you help me to find the languages that are meant,so I can draw the DFAs?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,869
Hello!!!
I have to draw the DFA of the language of the following expressions:
a){[tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex]}
b)[tex](\{\{1,0\}^{*},(\varnothing,2)^*\})^{*}[/tex]

Could you help me to find the languages that are meant,so I can draw the DFAs?
Hi evinda!! :)

Effort?
What do you already know about DFA's and what they look like?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Hi evinda!! :)

Effort?
What do you already know about DFA's and what they look like?
I know how to draw DFAs when I have a language,but I don't know how to find the language that is represented from the expressions above. :confused:

For example,if I had to draw the DFA,that accepts the language that contains the substring 001,I would do it like that:


dfa_001.jpg
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
How can I find,in general,the language of a regular expression?? :confused:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
How can I find,in general,the language of a regular expression??
This is just a remark (and a way to subscribe to the thread). There is no such thing as "finding the language" unless the language is finite. If the language is infinite, you cannot communicate or learn it as a set of words. Instead, you have to communicate some finite description of the language. Now, there is no canonical representation of a regular language. It can be described by a finite automaton, a regular expression, or a formula in first-order logic, and none of these is a priori better than the rest. For example, as you get familiar with regular expressions, they may become your preferred representation of regular languages.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
This is just a remark (and a way to subscribe to the thread). There is no such thing as "finding the language" unless the language is finite. If the language is infinite, you cannot communicate or learn it as a set of words. Instead, you have to communicate some finite description of the language. Now, there is no canonical representation of a regular language. It can be described by a finite automaton, a regular expression, or a formula in first-order logic, and none of these is a priori better than the rest. For example, as you get familiar with regular expressions, they may become your preferred representation of regular languages.
I understood...I tried to draw the finite automaton of the regular expression {[tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex]} and that's what I did.Is this right? :)
aut.jpg
 
Last edited:

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Or am I wrong???If we have this: [tex] \{00,010,\varnothing\}[/tex],do the automaton has to read all of these: [tex] 00,010,\varnothing\ [/tex] or just one of them?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
I tried to draw the finite automaton of the regular expression {[tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex]} and that's what I did.Is this right?
Notations for regular expressions differ. Does comma denote alternation? Is there a difference between curly braces and parentheses? Why is the complete expression surrounded by curly braces?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Notations for regular expressions differ. Does comma denote alternation? Is there a difference between curly braces and parentheses? Why is the complete expression surrounded by curly braces?
Oh sorry, the complete expression is not surrounded by curly braces. It is: [tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex].

With the parentheses I think that it is meant that $0$ is followed by $1$ and this sequence appears $n$ times with $n \geq 0$.

And in the curly braces the comma may denote the alternation.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,869
Oh sorry, the complete expression is not surrounded by curly braces. It is: [tex]1^*\{00,010,\varnothing\}(01)^{*}[/tex].

With the parentheses I think that it is meant that $0$ is followed by $1$ and this sequence appears $n$ times with $n \geq 0$.

And in the curly braces the comma may denote the alternation.
Looks like your off in the right direction!! :D

Except... that with the commas between {} that mean alternation, your graph should be slightly different...
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
I tried it again, is it maybe like that?
f_a.jpg
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,869
Looking good! ;)

One problem left. There is no such thing as an $\varepsilon$ transition.
It would be "no-input", which would not be deterministic.

Can you think of another (deterministic) transition that accepts either a '0' or a '1' that will show the same behavior?
And/or perhaps no transition at all, but marking the state as a final state?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Here is my version.



Missing arrows lead to sink.

Edit: Made the initial state to be also accepting in order to accept 1*. Still no warranty. :)
 
Last edited:

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Thank you very much!!! :rolleyes: