Regular Expression in Theory of Automata and Computation

In summary: Otherwise, I would just try to understand the problem as best as possible and come up with a reasonable solution. Unfortunately, I don't have enough information to give a definitive answer. In summary, the conversation discusses a regular expression problem in two parts. The first part involves finding a correct expression for blocks of consecutive symbols containing at least 2 a's. The given answer in notes is incorrect, as it allows for an incorrect string. The second part involves comparing two possible answers, where one is more complicated and the other is simpler but not equivalent. The conversation also discusses the definition of regular expressions and the need for clarification from an instructor.
  • #1
Crystal037
167
7
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)2)*+((a+b)3)*
and ((a+b)2)**((a+b)3)*
 
Physics news on Phys.org
  • #2
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 R2 means "RR" then (a+b)2 admits "aa", "ab", "ba" or "bb" which is not going to help.
 
Last edited:
  • Like
Likes FactChecker
  • #3
pbuk said:
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 R2 means "RR" then (a+b)2 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
 
  • #4
$$((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.
 
Last edited:
  • #5
Jarvis323 said:
$$((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
 
  • #6
Crystal037 said:
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.
 

Related to Regular Expression in Theory of Automata and Computation

1. What is a regular expression?

A regular expression is a sequence of characters that defines a pattern used to match strings in a given language. It is a powerful tool in the field of automata and computation, as it allows for efficient searching and manipulation of strings.

2. How are regular expressions used in automata theory?

Regular expressions are used to describe the patterns and rules of a language in automata theory. They can be used to define the states and transitions of a finite automaton, which is a mathematical model used to recognize and generate regular languages.

3. What is the difference between a regular expression and a regular language?

A regular expression is a notation used to describe a regular language, which is a set of strings that can be generated by a finite automaton. While a regular expression is a concise way of representing a language, a regular language is the actual set of strings that can be recognized by a finite automaton.

4. Can regular expressions be used to match complex patterns?

Yes, regular expressions can be used to match complex patterns by combining simpler expressions with logical operators such as "or" and "and". This allows for the creation of more sophisticated patterns that can match a wider range of strings.

5. Are regular expressions limited to just text matching?

No, regular expressions can be used for more than just text matching. They can also be applied to other types of data, such as DNA sequences, network protocols, and even images. As long as the data can be represented as a string, regular expressions can be used to manipulate and analyze it.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
3
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
942
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
703
  • Engineering and Comp Sci Homework Help
Replies
5
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
400
  • Special and General Relativity
Replies
10
Views
1K
Replies
9
Views
826
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top