CODEWITHSUNDEEP
regexautomationregular-language
bruteandbrains
bruteandbrains

Reputation: 11

Automata - Regular Expression

I've been trying to make a regular expression from the below:

L = {01, 0011, 000111, 00001111, 0000011111, 000000111111, ...}

but I just could not figure it out. The first thing that came to my mind was

0(0)^* 1(1)^*

Is there an app where I could test it out?

If this can't be done through Regular Expression, can an NFA or DFA be done?

but I'm not sure if that is the answer to the language. Could some good Samaritan kindly help me with this? Appreciate it.

Upvotes: 1

Views: 573

Answers (2)

sp00m
sp00m

Reputation: 48807

A subroutine may suit your needs:

(?<!0)(0(?1)?1)(?!1)

Regular expression visualization

Debuggex Demo

(?1) means recall the pattern captured in the first group, i.e. between the parens. This isn't available in all regex engines though - neither is the (negative) lookbehind (?<!...) by the way.

The difference between (?1) and \1 is that (?1) recalls the captured pattern while \1 recalls the captured data.

Upvotes: 4

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

I don't know about what you meant when you said that it should be regex, because it is mentioned automaton/regular expression too.

As per the automata theory :-

If you are talking about the regular expression for this formal language (having equal number of 0's and 1's and all 0's must be followed by 1's), it is not a regular language. It can be proved using the pumping lemma that this language is not regular.

But, this language can be expressed as {0i1i | i>0}; i belongs to set of positive integers.

Upvotes: 1

Related Questions