Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#1 2013-12-15 21:12:22

evinda
Full Member

Offline

Regular expression

Hi!!

R=



I have this regular expession and have to draw the DFA..But I haven't understood which language is meant..Could you give me a hint? hmm

Last edited by evinda (2013-12-15 21:13:36)

#2 2013-12-16 03:07:54

bobbym
Administrator

Online

Re: Regular expression

Hi;

I know what a regular expression is but I have no idea how to use it with cellular automata.

Have you tried the Stack Exchange or Stack Overflow?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#3 2013-12-17 06:30:50

evinda
Full Member

Offline

Re: Regular expression

bobbym wrote:

Hi;

I know what a regular expression is but I have no idea how to use it with cellular automata.

Have you tried the Stack Exchange or Stack Overflow?

I found similar questions with helpful answers there!Thanks for the hint wink

#4 2013-12-17 07:34:18

anonimnystefy
Real Member

Offline

Re: Regular expression

Hi evinda

Am getting a DFA with 5 states.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#5 2013-12-17 08:29:50

evinda
Full Member

Offline

Re: Regular expression

anonimnystefy wrote:

Hi evinda

Am getting a DFA with 5 states.

I tried to draw a DFA and I also got one with 5 states!!!!

#6 2013-12-17 09:08:29

anonimnystefy
Real Member

Offline

Re: Regular expression

Below is what I am getting.


Uploaded Images
View Image: DFA1.png      


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#7 2013-12-17 09:45:24

evinda
Full Member

Offline

Re: Regular expression

anonimnystefy wrote:

Below is what I am getting.

I got a similar!!! smile Thank you very much!!!! wink

#8 2013-12-17 22:49:58

gAr
Star Member

Offline

Re: Regular expression

Hi evinda,

I understood the language to be



Since there are algorithms to convert from RE to NFA to DFA to minimized DFA, someone has written a software for that: JFLAP

Enter the RE as: 1*(00+010+!)(01)*

edit: corrected the RE

Last edited by gAr (2013-12-18 03:07:02)


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

#9 2013-12-17 23:17:29

gAr
Star Member

Offline

Re: Regular expression

1. After entering the RE, choose convert->"convert to NFA"
2. "Do All" and "export"
3.  Convert->"convert to DFA" and "complete" and "Done"
4. Convert->"minimize DFA". Select root of the tree and "complete subtree", and "Finish"
5. Click "complete" and "Done"


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

#10 2013-12-18 01:24:34

gAr
Star Member

Offline

Re: Regular expression

I was unable to upload earlier, this is the DFA I got.


Uploaded Images
View Image: mindfa.png      


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

#11 2013-12-18 02:04:10

anonimnystefy
Real Member

Offline

Re: Regular expression

Where did you get the third Kleene star from?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#12 2013-12-18 03:05:54

gAr
Star Member

Offline

Re: Regular expression

My bad, here is the diagram we get for the corrected expression.


Uploaded Images
View Image: mindfa2.png      


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

#13 2013-12-18 03:24:26

anonimnystefy
Real Member

Offline

Re: Regular expression

Doesn't that DFA also accept 0101?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#14 2013-12-18 03:42:48

gAr
Star Member

Offline

Re: Regular expression

It's expected since we can choose


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

#15 2013-12-18 06:36:54

anonimnystefy
Real Member

Offline

Re: Regular expression

We can chose epsilon only once...


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#16 2013-12-18 14:16:29

gAr
Star Member

Offline

Re: Regular expression

epsilon from 1* and next epsilon from (00+010+!)


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Board footer

Powered by FluxBB