4. Textbook page 63: 2.1a, 2.5, 2.6 2.1 Given the FSM shown, (a) draw the state diagram (final state: 3) For each string, is it accepted: aaaaa, bbbbb, ababa, babab, abbbb Also: Describe in English if possible (or regular expression if you like) 2.5 Show that RS != SR by giving a counterexample 2.6 Show that (R | S)* != (R* | S*) by giving a counterexample. Also Is (R | S)* = (R* | S*)* ? Yes, no and why

a b

1 2 3

2 1 2

3 1 3

2.3. For each of the NFAs in Problem 2.2, construct the equivalent DFA. 2.4. Show that (RIS)" = (R*S*)" 2.5. Show that RS SR by giving a counterexample. 2.6. Show . 2.7. Given the RE R- (ablb)*c, which of the following strings is (are) in L(R)? 63 that (RIS) * (R*|s*) by giving a counterexample ababbc c babc abab 2.8. Given the RE ab c(alb)c, which of the following strings is (are) in L(R acac acbbbc abcac abcc 2.9. If = {a, b), write a regular expression whose language is all 2.10. If = {a, b), write a regular expression whose language is all strings 2.11. If = {0, 1), write a regular expression whose language is all strings 2.12. If = {0, 1, write a regular expression whose language is all strings in 2.13. Construct an NFA that recognizes the RE alb*, and find the equivalent 2.14. Construct an NFA that recognizes the RE a(abe)*, and find the equivalent 2.15. Use the Pumping Lemma to show that the language, L215 = {a" ben, n > 2.16. Test the language L2 16 = {(ab , n > 0} with the Pumping Lemma and 2.17. Using the Pascal state table, trace the lexical scan of the following strings: beginning and ending with b. whose length is a multiple of 3. containing exactly three 1s. which every 1 is followed by at least one 0. DFA. DFA. 0) is not regular. show that it is regular. k x var x:integer; if (a>b) or (a