0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I think : [[1]] the centre State is $q1$ , not $a1$ [[2]] the last State $q3$ must have $a,b,c$ , not $b,c$ [[3]] $q0$ , $q1$ , $q2$ are good (valid) terminal States , while $q3$ is bad (invalid) terminal State. Are these assumptions correct ? $\endgroup$
    – Prem
    Commented Dec 25, 2022 at 10:17
  • 1
    $\begingroup$ Yes you are right, the q3 state should have also 'a' and the a1 state it was a spelling mistake it should be q1 $\endgroup$
    – dy 1995
    Commented Dec 25, 2022 at 10:29

1 Answer 1

0
$\begingroup$

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$"

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .