Regular expression to NFA-confusing regular expressions-:

In summary, the conversation is about the creation and conversion of a regular expression to an NFA, and the clarification of the language it accepts. The regular expression is simplified by adding an epsilon transition. The need for this transition is questioned, but it is explained that it is necessary to choose one option from the regular expression, similar to choosing a store to buy a new gaming console from.
  • #1
shivajikobardan
674
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
  • #2
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?
 

1. What is a regular expression?

A regular expression is a sequence of characters that forms a search pattern. It is commonly used to find and match specific patterns of text within a larger body of text.

2. How can I convert a regular expression to an NFA?

The conversion process from a regular expression to a non-deterministic finite automaton (NFA) involves breaking down the regular expression into smaller components and constructing a state diagram based on the rules of regular expression syntax.

3. What makes regular expressions confusing?

Regular expressions can be confusing due to their complex syntax and the use of special characters and metacharacters that have specific meanings. Additionally, there are multiple variations of regular expression syntax, which can add to the confusion.

4. Can I use a regular expression to match any string?

Yes, regular expressions can be used to match any string of characters. However, the specific pattern you use may not always capture all possible variations of a string. Regular expressions are powerful but may require some trial and error to find the most effective pattern for a given task.

5. Are there any limitations to using regular expressions?

While regular expressions are a useful tool for pattern matching, they do have some limitations. They may not be the most efficient solution for complex matching tasks, and they may not be suitable for all types of data, such as structured data or images.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
896
  • Programming and Computer Science
Replies
6
Views
3K
  • Programming and Computer Science
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
8
Views
2K
  • Other Physics Topics
Replies
1
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
3
Views
277
  • Sticky
  • Engineering and Comp Sci Homework Help
Replies
1
Views
19K
Back
Top