Create regular expression not contain "aaa"

133 Views Asked by At

I have a question about creating regular expression out of the given language.

The language is : 3 = {∈{,,}∗| }

I've created the following DFA (Im sorry can't post images because need to have 10 rep)

considering the DFA is ok I'm trying to create a regular expression using the blocks method.

the strat should be $$(b+c)^\ast$$ because I can use 'b' or 'c' how much I want. The is should be $$(b+c)^\ast (as)^\ast$$ when $$s = (\epsilon+b+c)(b+c)(b+c)^\ast$$

1

There are 1 best solutions below

0
On BEST ANSWER

I think this will work out :

$((b+c)^*(ab+ac)^*(aab+aac)^*)^*$

Here I am trying to State that :

Initially , $b$ or $c$ can occur Indefinite number of times (including 0 times)
which can then have following $ab$ or $ac$ both Indefinite number of times (including 0 times)
which can then have following $aab$ or $aac$ both Indefinite number of times (including 0 times)
then this whole thing can occur Indefinite number of times (including 0 times)

Here , the IMPLICIT Condition is that $aaa$ can not occur.
[[ Every "$a$" has a following "$b$" or "$c$". When the "$a$" has following "$a$" itself , to give "$aa$" , then the following must be "$b$" or "$c$" , hence there can never be "$aaa$" , where "$a$" occurs "$3$" or "$4$" or more times. ]]

We can easily check that these will be in that language :
"$ $" , "$b$" , "$bc$" , "$babacac$" , "$bcaabaacaac$" , "$bcacaabbabaac$"

We can then check that these will not be in that language :
"$aaa$" , "$baaa$" , "$aaabc$" , "$babacacaaa$" , "$bcaaabaacaac$" , "$bcacaabbabaacaaa$"