Give regular expressions for the following languages on the alphabet {a, b}. (a)

Question

Give regular expressions for the following languages on the alphabet {a, b}.

(a) the set of all strings with an even number of a’s

(b) the set of strings in which all runs are of length < 3. (A run in a string is a non-extendable substring of length at least 2 which contains repetitions of the same symbol. For example (a) the string abab has no runs, (b) the string aabbbababbaaa has four runs, in order: a run of length 2 of a’s, a run of length 3 of of b’s, a run of length 2 of b’s and a run of length 3 of a’s.)

Explanation / Answer

Give regular expressions for the following languages on the alphabet {a, b}.

Q. the set of all strings with an even number of a’s

(ab*ab*)*

ab*-> at least one a with any number of b’s

(ab*ab*)* -> any combination of ab*(twice) for even-ness

Q. the set of strings in which all runs are of length < 3.

(aab+bba)*(+a+aa+b+bb)

aab->run of a’s length 2

bba->run of b’s length 2

a,b->default run of 1

aa,bb->run of length 2 of each a,b

(A run in a string is a non-extendable substring of length at least 2 which contains repetitions of the same symbol. For example (a) the string abab has no runs, (b) the string aabbbababbaaa has four runs, in order: a run of length 2 of a’s, a run of length 3 of of b’s, a run of length 2 of b’s and a run of length 3 of a’s.)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.