(i) Let us reconsider the regular expression (a + b)*a(a + b)*b(a + b)* Show that this...

Question:

(i) Let us reconsider the regular expression

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

Show that this is equivalent to

(a + b)*ab(a + b)*

In the sense that they define the same language.
(ii) Show that

(a + b)*ab(a + b)* + b*a* = (a + b)*

(iii) Show that

(a + b)*ab[(a + b)*ab(a + b)* + b*a* ] + b*a* = (a + b)*

(iv) Is (iii) the last variation of this theme or are there more beasts left in this cave?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction To Computer Theory

ISBN: 9780471137726

2nd Edition

Authors: Daniel I. A. Cohen

Question Posted: