regular expressions!

[evinda]

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]

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]

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.

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

 

[evinda]

How can I find,in general,the language of a regular expression??

 

[Evgeny.Makarov]

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]

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?

 

[evinda]

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]

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]

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]

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

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

 

[evinda]

I tried it again, is it maybe like that?

 

[Klaas van Aarsen]

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]

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.

 

[evinda]

Thank you very much!!!