Regular expression to NFA-confusing regular expressions-:

Click For Summary
SUMMARY

The discussion centers on converting the regular expression R=(01+010)* into a Non-deterministic Finite Automaton (NFA). The user expresses uncertainty about the conversion process and the necessity of epsilon transitions. It is established that the language defined by the regular expression R=(01+010)* includes strings like 01010, while the alternative expression R=(01)*+(010)* does not accept the same language. The need for epsilon transitions is highlighted as a crucial step in understanding the NFA construction.

PREREQUISITES
  • Understanding of regular expressions and their syntax
  • Familiarity with Non-deterministic Finite Automata (NFA)
  • Knowledge of epsilon transitions in automata theory
  • Basic concepts of formal languages and automata
NEXT STEPS
  • Study the construction of NFAs from regular expressions using tools like JFLAP
  • Learn about epsilon transitions and their role in automata theory
  • Explore the differences between deterministic and non-deterministic finite automata
  • Investigate the implications of regular expression variations on accepted languages
USEFUL FOR

Students and professionals in computer science, particularly those focusing on automata theory, formal languages, and compiler design.

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?
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
4K
Replies
2
Views
2K
  • · Replies 2 ·
Replies
2
Views
10K
  • · Replies 3 ·
Replies
3
Views
2K