Finding a regular expression [closed]

Question

I have a simple question about finding a regular expression for a given language.

I am given the language L where:

L = {w ∈ {0, 1}* : w has exactly one pair of consecutive zeros}

My first attempt at this was to try L( (0 + 1)* 00 (0 + 1)*), but I noticed the problem with that would be with where I have (0 + 1)* because if 0 is chosen, it can be zero more more of them, thus leading to more than one pair of consecutive zeros.

I also know, that the possible cases I have are, two zeros in the front, in the middle, and at the end. I just am not quite sure how to create a regular expression for that.

Any help is much appreciated.

Illtreat

Answer 1

Try this:

1* (011*)* 00 (11*0)* 1*

An explanation:

• 1*: any amount of leading 1’s
• (011*)*: if there is a 0 before the 00, it must not be followed by another 0, thus only one or more 1’s are allowed; this pattern may be repeated any number of times
• 00: the two 0’s
• (11*0)*: if there is a 0 after the 00, it must not preceded by another 0, thus only one or more 1’s; this pattern may be repeated any number of times
• 1*: any amount of trailing 1’s

Arachnoid

@brianary: In this case “+” is the alternation operator. So “0 + 1” is either “0” or “1”. – Arachnoid

in some books 1+ is the same thing as 11* . it just depends on where you're getting your theory from. – Becerra

@Arthur Rizzo: It depends on how the syntax of regular expressions is defined. I’ve learned it with “+” as alternation operator while others use “|”. – Arachnoid

It seems unusual to teach theory in a dialect that differs so fundamentally from implementations. – Brianna

@brianary: I think in most theory classes "one or more 1's" is written 1^+ (i.e. the plus is in a superscript). Most implementations don't have superscripts, so they just bring the plus down. It is confusing because it disagrees with the standard use of plus (which is 'or'), but I think that's a limitation of typesetting, not really an issue with either the theory or the implementation. Some theorists (notably Sipser) use the union operator instead of the plus to avoid this confusion. – Inotropic

@brianary: The basic regular expression syntax in theory class is often only alternation (α+β), concatenation (αβ), repetition (α*), and grouping ((α)). More advanced syntax as we know it from modern regular expression implementations is only syntactic sugar: α? → (ε+α), α+ → αα*, [abc] → (a+b+c), etc. – Arachnoid

Where is this syntax documented? Is it broadly accepted, or a single textbook? I still feel that it is harmful or at least questionable to unnecessarily use a different syntax for theory than is used in any real language. Especially since this is one area where there is so little inconsistency in implementations. – Brianna

Answer 2

The best possible answer for this problem is (1 + 01)* 00 (1 + 10)*

Reggiereggis

Answer 3

i believe it would be like this

((1*)(01)*))* 00 ((11*)0)*1*

Becerra

Answer 4

The sequence:

• Anything but 00, ending with 1
• 00
• Anything but 00, starting with 1

Conjugated

Answer 5

My answer would be : (1 + 01) 00 (1 + 10)**

Explanation:

The consecutive zeros shouldn't be preceded or followed by another zero. Hence 00 should be preceded by a 1 which can be either a 1 or 01. It can be followed by a 1 or 10.

Slimsy

Answer 6

It is wrong try 00110011 it must not be Satisfied But here it is satisfying Take firstly the pair 00 then take 110 Then take 011 So in whole it would be 00110011 that it is satisfying so it is wrong

Insensitive

Welcome to Stack Overflow! Thank you for your answer. Please provide more details about your solution. Code snippets, high quality descriptions, or any relevant information would be great. Clear and concise answers are more helpful and easier to understand for everyone. Edit your answer with specifics to raise the quality of your answer. For more information: How To: Write good answers. Happy coding! – Outwardly