Michael Sipser Edition 3 Exercise 1 Question 20 (Page No. 86)

Question

For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts.

1. $a^{*}b^{*}$
2. $a(ba)^{*}b$
3. $a^{*}\cup b^{*}$
4. $(aaa)^{*}$
5. $\Sigma^{*}a\Sigma^{*}b\Sigma^{*}a\Sigma^{*}$
6. $aba\cup bab$
7. $(\epsilon\cup a)b$
8. $(a\cup ba\cup bb)\Sigma^{*}$

Answer 1

           Examples as per the language provided : 

(A.)   accepted string = { epsilon, ab}

         non accepted string = { ba, bab }

(B.)    accepted string = { ab, abab }

          non accepted string = { b, ba }

(C.)    accepted string = { aa, b }

          non accepted string = { ab, ba }

(D.)   accepted string = { epsilon , aaa }

         non accepted string = { b , bb }

(E.)   accepted string = { aba, aaba }

         non accepted string = { a, b }

(F.)   accepted string = { aba , bab }

         non accepted string = { a, b }

(G.)   accepted string = { b , ab }

         non accepted string = {a , epsilon }

(H.)   accepted string = { a, ba }

         non  accepted string = { epsilon , b }