CS 321 HW2

1) (8pts) Given an NFA M with the transition graph shown below.

a) Give a regular expression r such that L(r)= L(M)

b) Construct a regular grammar G such that L(G)= L(M)

CS 321 HW2 Submit typed solutions created using a word processor or text editor as a pdf file to Canvas. For any solutions involving an NFA or DFA also submit the.jff JFLAP files. 1) (8 pts) Given an NFA M with the transition graph shown below. a) Give a regular expression r such that L(r) = L(M) b) Construct a regular grammar G such that L(G) = L(M) 2) (8 pts) Given the regular grammar G = (V, S, T, P) where V = { A, B, C, S}, T = {0, 1) and productions P defined below, 5 00A 1B A OA | B11C1 C OB a) Construct an NFA M such that L(M)=L(G) b) Give a regular expression r such that L(r)=L(G) 3) (4 pts) Suppose that a bank only permits passwords that are strings from the alphabet = (a, b, c, d, 1, 2, 3, 4} that follow the rules: The length is at least five characters It begins with a letter {a,b,c,d} It ends with two digits {1,2,3,4} The set of legal passwords forms a regular language L. Construct a regular expression r such that L(r) = L. 4) (5 pts) Prove that if L is regular language then LP is a regular language