1. Give regular expressions for each of the following subsets of ta, (a) {x | x
ID: 3887854 • Letter: 1
Question
1. Give regular expressions for each of the following subsets of ta, (a) {x | x contains an even number of a's) (b) { z contains an odd number of b's) (c)( z contains an even number of a's or an odd number of b's} (d) {x | x contains an even number of a's and an odd number of b's} Try to simplify the expressions as much as possible using the algebraic laws of Lecture 9. Recall that regular expressions over {a, b} may use e, ø, a, b, and operators +, *, and only; the other pattern operators are not allowed.Explanation / Answer
even -> (a (bb)* a (bb)* | a b (bb)* a b (bb)*)
odd -> (a b (bb)* a (bb)* | a (bb)* a b (bb)*)
even number of a or odd number of b -> ((bb)* b (aa)* )* ((aa)* b (bb)*)
even number of a and odd number of b -> (bb)* b (aa)* + (aa)* b (bb)*
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.