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
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.