Let = {0,1} and for i = N, let L; be the language: L = {w...

 

Transcribed Image Text:

Let = {0,1} and for i = N, let L; be the language: L = {w * The i-th last symbol in w is 1} (a) Show that Li can be accepted by an NFA with i + 1 states. (4 marks) (b) Show that a minimal DFA that accepts L; needs at least 2 states. (Hint: consider the Myhill-Nerode equivalence classes of all words of length i) (6 marks) Let = {0,1} and for i = N, let L; be the language: L = {w * The i-th last symbol in w is 1} (a) Show that Li can be accepted by an NFA with i + 1 states. (4 marks) (b) Show that a minimal DFA that accepts L; needs at least 2 states. (Hint: consider the Myhill-Nerode equivalence classes of all words of length i) (6 marks)