Regular Expressions for Strings with Specific Character Patterns

Click For Summary
SUMMARY

The discussion focuses on constructing regular expressions for specific character patterns using the alphabet Σ = {a, b} and Σ = {a, b, c}. The proposed solutions include: for strings with no more than 3 'a's, the expression is b*Ub*ab*Ub*ab*ab*Ub*ab*ab*ab*; for strings with 'a's divisible by 3, the expression is (b*Ub*ab*ab*ab*)*; and for strings containing the substring 'aaa' exactly once, the expression is b*(aUaaUe)b*aaab*(aUaaUe)b*. Additionally, the user inquires about a regular expression for strings containing at least one 'a', one 'b', and one 'c', proposing (a(bUc)*Ub(aUc)*Uc(aUb)*)*, while the book provides (aUbUc)*c(aUbUc)*b(aUbUc)*a(aUbUc)* as the correct solution.

PREREQUISITES
  • Understanding of regular expressions and their syntax
  • Familiarity with the concepts of finite automata
  • Knowledge of string patterns and character sets
  • Basic proficiency in theoretical computer science
NEXT STEPS
  • Study the construction of regular expressions for finite automata
  • Learn about the Pumping Lemma for regular languages
  • Explore the differences between deterministic and non-deterministic finite automata
  • Research advanced regular expression features in programming languages like Python or JavaScript
USEFUL FOR

Students preparing for exams in theoretical computer science, software developers working with string manipulation, and anyone interested in mastering regular expressions for pattern matching.

kliker
Messages
102
Reaction score
0

Homework Statement


Σ = {a,b}
find regular expression for

1)all strings that haven't got more than 3 a's
2)all strings that have a number of a's that is divisible by 3
3)all strings that have the substring aaa only one time

The Attempt at a Solution


1) b*Ub*ab*Ub*ab*ab*Ub*ab*ab*ab*

2) (b*Ub*ab*ab*ab*)*

3) b*(aUaaUe)b*aaab*(aUaaUe)b*

can you please tell me if I am correct? this is not homework actually but i didnt know where to post it, I am just preparing myself for the upcoming exams and need to know if i have these correct

thanks in advance
 
Physics news on Phys.org
i have one more

Σ = {a,b,c}

i want a regular expression for all strings that contain at least 1 a, 1 b and 1 c

ok my solution is this

(a(bUc)*Ub(aUc)*Uc(aUb)*)*

but the book has this solution

(aUbUc)*c(aUbUc)*b(aUbUc)*a(aUbUc)*

which is right but is my solution wrong?
 

Similar threads

  • · Replies 14 ·
Replies
14
Views
3K
  • · Replies 2 ·
Replies
2
Views
9K
  • · Replies 20 ·
Replies
20
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 3 ·
Replies
3
Views
4K
Replies
1
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 46 ·
2
Replies
46
Views
9K