MHB Regular expression to NFA-confusing regular expressions-:

AI Thread Summary
The discussion centers on converting the regular expression R=(01+010)* into a non-deterministic finite automaton (NFA) and understanding its accepted languages. It is noted that the language described by the expression (01+010)* includes sequences like 01010, which are not captured by the alternative expression (01)*+(010)*. The need for epsilon transitions in the NFA is questioned, with an analogy provided to clarify their importance in decision-making processes. The conversation highlights the complexity of regular expressions and their corresponding NFAs. Ultimately, the regular expression is acknowledged as a straightforward representation of the language it describes.
shivajikobardan
Messages
637
Reaction score
54
R=(01+010)*
For it I made the below nfa which i believe seems correct. Plus the tutorials that I am following also make sure it’s correct. Q0 is initial state(forgot to mention in figure).
https://lh6.googleusercontent.com/GUZlDA7_UjNWlcNx76e1xHOYhNjYBzbDMnP9qBnMjL8ux_Ntz3SSVIcw-VfMR6jbFlbxYG3nx6ccd2gWObG2hXnmXLE14mKI4PtFf4GtDc_PgenECvC_h_m9Yrbrg99hHZh258F9

R=(01)*+(010)*

But idk how to convert this to NFA
What will be languages accepted by this NFA? Won’t it be the same as the above one?

(for some different question)
I got small hint about this. It was to add epsilon transition, but I don’t understand the need for it.
https://lh3.googleusercontent.com/naVKgIC_8oj_v6TLAyjAhdOlLEpr4jsUAiYNw59d-2LifF5scOxn7rBw0AwCvmDwtFMZtv-s7DfXZAkt5OTNOksg7PNgzhEhyEXJ1JRmtN4nIELpWrJCIUaKA7uvrJatk6oTbd2k
Source-: https://www.cs.wcupa.edu/rkline/fcs/nfas.html
 
Technology news on Phys.org
shivajikobardan said:
What will be languages accepted by this NFA?
I believe the regular expression offers the simplest description of this language.

shivajikobardan said:
Won’t it be the same as the above one?
The language $(01+010)^*$ contains $01010$, but $(01)^*+(010)^*$ does not.

shivajikobardan said:
(for some different question)
Why do you think that this is a different question if the regular expression is the same up to replacement of 0 and 1 by $a$ and $b$?

shivajikobardan said:
It was to add epsilon transition, but I don’t understand the need for it.
Well, this is surprising if you understand the meaning of regular expressions. If you learned that the new gaming console would be sold at two stores only and you wanted to buy it, how can it be unclear that the first thing you need to do is to choose one of the stores and go there?
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...

Similar threads

Back
Top