1. (22 points) (a) Let E = a0\" + b0 be a regular expression over = {a, b, 0.1).
ID: 3594070 • Letter: 1
Question
1. (22 points) (a) Let E = a0" + b0 be a regular expression over = {a, b, 0.1). Which of the following is a string in L(E): (circle all that are correct) (a) a0* (b) e (c) aa00 (d) (e) b (f) none of those choices (b) A student ID number is an 8-digit number. There is a DFA M such that L(M) = {ID numbers of currently registered students at UVic) which will en- able the university to check if an ID number belongs to some student using 8 steps in the DFA T F (c) A student password is made up of letters and numbers and has arbitrary length. There is a DFA M which can check if a student has entered a password, followed by a carriage return, followed by a repeat of the same password using 2*(length of the password) +1 transitions T F (d) Let M be an NFA. When M receives w as input, if there is a computation path which does not end in an accept state then this implies w ¢ L(M) T F (e) If A and B are regular languages, then the language PS = {wu I w is a prefix of A and u is a suffix of B} is always regular. T F (f) Every subset of a regular language is a regular language T FExplanation / Answer
(A)
-Here E= a0*+b(phi) , + means OR so either starting with single a and zero or more 0’s are ok or starting with b and nothing ahead is ok.
-So here, option (a) a0* and option (e) b are correct.
(B)
-DFA is L(M)={ID number of currently registered students at UVic} .Here to check the student ID number belongs to some student will not require to go through 8 steps because it may happen that we come to know that ID is incorrect in 2-3 steps as well.
-Thus this is false (F).
(C)
-Here we will not require to check for 2*(length of the password) + 1 transitions because it does not requires this much transitions.
- Thus this is false (F).
(D)
-If the computation path does not ends in the accept state then the input will not belong to the language either in NFA or in DFA. Thus w does not belongs to L(M).
-This is true (T).
(E)
-We cant say that if A & B are regular languages then PS is also regular.
- Thus this is false (F).
(F)
-True. Every subset of a regular language is a regular language.(T)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.