Search code examples
regexformal-languages

Regex create a expression solving the following pattern


This is part of a university optional homework and we are kinda struggling a bit.

The pattern to solve isn't that hard to be honest we don't get our heads around it, create a expression that has the alphabet {a,b,c} contains at least one a and one b.

current two approaches are

(a|b|c)*a(a|b|c)*b(a|b|c)* or (a|b|c)(a|b)(a|b|c)*(a|b)(a|b|c)*

But both of these have flaws first one wouldnt allow ccbacc second one would allow ccaacc.

Greetings


Solution

  • There can be two rules to produce the requirement, one is an a before a b:

    S₁ → [abc]* a [abc]* b [abc]*
    

    the other is a b before an a

    S₂ → [abc]* b [abc]* a [abc]*
    

    Now just combine them together using the alternative operator,

    S → S₁ | S₂
      = [abc]* a [abc]* b [abc]* | [abc]* b [abc]* a [abc]*
    

    This can be simplified using the rule AB|AC = A(B|C) and AC|BC = (A|B)C:

    S → [abc]* (a [abc]* b | b [abc]* a) [abc]*
    

    I assume your homework only deals with formal language. In real programming, just use indexOf or similar functions to find out if a string contains an a and a b. Regex is too heavy for this task.