2

I need to write a regular expression rule where the expressions I have doesn't have a recursive rule.

For example, if I need to write an expression where I can have any number of a's, b's, c's, and d's but not have any a's and d's immediately following any b's. a's and d's can appear later in the string though.

Here are all the rules I can use: rules Tried this: (a|d)* (c|b)* c* (a|d)*. However, as you can see, I would need to keep repeating to make this work. Any help would be appreciated!

Improve this question
5
  • 1
    Can you give an example of accepted words and rejected words? Commented Sep 18, 2015 at 7:34
  • 1
    @stribizhev he does not ask about posix regex but regular expression Commented Sep 18, 2015 at 7:36
  • I can only use what you see in the picture. So I can't use the expression you used above. So, for example, just writing a would only one a. Writing a* could be { Epsilon, a, aa, aaa, aaaa...}. Something like ax* would be like {ax, axx, axxxxxx, ...}. Commented Sep 18, 2015 at 7:38
  • 1
    What about this one? I do not know if you can or intend to use anchors though. Commented Sep 18, 2015 at 7:43
  • Thanks, but you're right. I can't use $,^. Commented Sep 18, 2015 at 7:48

2 Answers 2

Reset to default
1

You need to rephrase the question.

I can have any number of a's, b's, c's, and d's but not have any a's and d's following any b's.

In other words, you can have (a|c|d) any number of times, but when if a b appears, then any number of (b|c): so, (a|c|d)* (b (b|c)*) | ɛ).

It is formally equal to (a|c|d)* (b|c)* (you might want to figure out why), but in practice, despite being shorter, this one is subject to catastrophic failure when evaluated by the common regexp algorithms.

(If you want to test it on computational/practical regexps, as opposed to theoretical ones, it translates to [acd]*(?:b[bc]*)?.)

EDIT: Yeah, misread the question. "immediately following" might have been a good word choice. How about...

(a|c|d|b+c)*(b|ɛ)
(?:[acd]|(?:b+c))*b?

Explaining the logic here, you can use any of the letters, but if you use b, you can go on with any number of bs but when you tire of that the next one needs to be a c (the only remaining one if you stopped b-ing and can't do a or c). Then it's back to the usual programme. At the end, you can have a b that is not necessarily followed by anything.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

How does that add any number of a's and d's after? For example, you can have abbbbcadadbca.
@Maru: Ooh, I misread! So, it blocks only immediately following b... Okay.
If I understand correctly, doesn't this have same problem as above? If you choose b then nothing, it loops back to beginning and you choose a or d again.
@Maru: Bleeh, I said it correctly in the explanation then kitten up in the code. Fixing now. Thanks.
1

You can build automata and convert it into regular expression. Since a and d cannot be after b:

enter image description here

And here only stated acd and b are accepted. START can also be accepted if you accept empty word.

So you can start with (a|c|d). It can repeat itself without changing state so (a|c|d)*. From state b you can go with b* OR one c - this gives b*|c -> (b(b*|c)). This gives in total (((a|c|d)*)|(b(b*|c)))*

Improve this answer

7 Comments

Nitpick: b|(b|c) is not correct - because it could give you bb, then you get again the unrestricted a|c|d choice following the second b.
There is no b|(b|c). Did you mean b(b|c) ?
Doesn't this allow aabba? It repeats (a|c|d) then you can pick bb because of the OR. Then go back to a or d? Maybe I'm not understanding the logic.
Right - c should be out of scope and escape regex since state is changing. Post updated
I think your updated code still has the same logical error. Because of (b*|c), a c can never be chosen. Thank you for all the help by the way. I learned a lot from this.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.