CODEWITHSUNDEEP
regexautomata
Tostack Overlow
Tostack Overlow

Reputation: 13

Automata regular expression {0+1}*

I'm new in Automata concept AND In some papers I found {0,1}* .

  1. Is it same as (0+1)*

  2. Also can we generate 101 from the (0+1)*

  3. can we generate 101 from the {0,1}*
    if 1) answer is NO

PLEASE any one help me to solve this confusion..

Upvotes: 1

Views: 14225

Answers (1)

nhahtdh
nhahtdh

Reputation: 56809

If all of them are found in computer science paper and computational theory books, then yes, they are likely the same.

  • In the notation {0,1}*, set notation {0,1} is used to denote "0 or 1".

  • Alternatively, + is also used to denote alternation (JFLAP, for example). So (0+1) can also mean "0 or 1".

  • | is also used to denote alternation (0|1) in theoretical computer science context. This is also the syntax for alternation in many regex engines.

The Kleene star * is, having the same notation in both theoretical regular expression (books, paper) and practical regex library, denotes repetition of 0 or more times of the preceding atom.

Since they mean "(0 or 1) repeated 0 or more times", both of them can generate the language 101.

As @Bergi mentioned in the comment, you should take a step back when you see both syntax being used in the same book/paper. For example, @paarandika noted that + can actually means "repeat once or more times" in book/paper if it is in superscript.

Upvotes: 4

Related Questions