2. Given the alphabet G = { a, b}. Give the regular expressions for the followin

ID: 3704750 • Letter: 2

Question

2. Given the alphabet G = { a, b}. Give the regular expressions for the following languages:

a) all strings with no more that three a’s

b) all strings with the number of a’s divisible by three.

c) all strings with exactly one occurrence of the substring aaa

3. Which of the following are true? Explain.

a) baa ? a* b* a* b*

b) (b* a*) ? (a* b*) = a* | b*

c) (a* b*) ? (b* a*) = ?

d) abcd ? (a (cd)* b)*

4. What is the language represented by each of the following regular expressions?

a) ((a* a) b) | b

b) (1 | 01)+

c) 1 (0 |1)* 0

d) (0 | 1)* 011(0 | 1)*

5. Which of the following strings belong to the language described by the regular expression 0*|(0*10*10*10*)*?

a) 1001101 f) 1001001

b) 000 g) 111

c) 110101 h) 11101101

d) 10001000 i) 11000101

e) 011001000111

2. Given the alphabet G = { a, b}. Give the regular expressions for the following languages:

a) all strings with no more that three a’s

b*(a+?)b*(a+?)b*(a+?)b*

Explanation

b) all strings with the number of a’s divisible by three.

(b*ab*ab*ab*)*

Explanation

c) all strings with exactly one occurrence of the substring aaa

(b* + ab + aab )aaa(b* + ab + aab )(a+aa+?)

Explanation

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