Regular Expression in Theory of Automata and Computation

[Crystal037]

Homework Statement

Find the regular expression to accept strings following the conditions given below:
(i)strings of a's and b's such that every block of 4 consecutive symbols contains at least 2 a's
(i)strings of a's and b's whose length is either even or a multiple of 3 or both

Relevant Equations

I will use E to denote epsilon that is empty string

In first part,since every block of 4 consecutive symbol contain at least 2 a's
The answer in notes is given
(aa(a+b)(a+b)+a(a+b)a(a+b)+a(a+b)(a+b)a+(a+b)aa(a+b)+(a+b)a(a+b)a+(a+b)(a+b)aa)⁺
But this wont be true since if we choose aabbbbaa which is possible according to the above regular expression, it wont be correct since there's a block with 4 consecutive b's
In 2nd part,
I have come up with 2 answers, are both of these same
((a+b)²)^*+((a+b)³)^*
and ((a+b)²)^**((a+b)³)^*

 

[pbuk]

In 2022 when we use the term "regular expression" most people think of "Perl compatible regular expressions" (PCRE); the syntax you are using is not PCRE, nor is it the same as anything else I have seen before. In particular it is more complicated than we usually use in the theory of automata.

Anyway, for your answers:
(i) I agree that the given expression admits aabbbbaa; either the question is poorly worded or the answer is wrong
(ii) Assuming (a+b) means "a or b" and R² means "RR" then (a+b)² admits "aa", "ab", "ba" or "bb" which is not going to help.

 

[Crystal037]

In 2022 when we use the term "regular expression" most people think of "Perl compatible regular expressions" (PCRE); the syntax you are using is not PCRE, nor is it the same as anything else I have seen before. In particular it is more complicated than we usually use in the theory of automata.

Anyway, for your answers:
(i) I agree that the given expression admits aabbbbaa; either the question is poorly worded or the answer is wrong
(ii) Assuming (a+b) means "a or b" and R² means "RR" then (a+b)² admits "aa", "ab", "ba" or "bb" which is not going to help.

This would give string of length 2, I have used a * kleen star above the whole thing, which will give multiples of 2

 

[Jarvis323]

$$((a+b)^2)^*+((a+b)^3)^*$$
$$((a+b)^2)^*((a+b)^3)^*$$

If the above is what you meant, the two aren't equivalent, because, as an example, the second one accepts strings of length 5, or 7, or $2k+3j$ in general.

I agree with pbuk that the first question is either worded in a misleading way or the solution in the notes is incorrect. I think they mean each block $$x_{4i}x_{4i+1}x_{4i+2}x_{4i+3}$$ contains 2 a's.

 

[Crystal037]

$$((a+b)^2)^*+((a+b)^3)^*$$
$$((a+b)^2)^*((a+b)^3)^*$$

If the above is what you meant, the two aren't equivalent, because, as an example, the second one accepts strings of length 5, or 7, or $2k+3j$ in general.

I agree with pbuk that the first question is either worded in a misleading way or the solution in the notes is incorrect. I think they mean each block $$x_{4i}x_{4i+1}x_{4i+2}x_{4i+3}$$ contains 2 a's.

ok and for the first part for the given question what should be the correct regular expression

 

[Jarvis323]

ok and for the first part for the given question what should be the correct regular expression

It wouldn't help to just give you an answer.

If there is a TA or instructor you can contact, I would ask them for clarification.