Minimum State Lemma. If there are k pairwise distingui shable strings with respect to a language L, then any DFA that recognizes L must have k or more states. Problem 1 a) Prove that the language Li is decidable. Li-( 1 Mi and M2 are DFAs with a finite alphabet and L(M)(M2) } Use the minimum-state lemma to prove that any DFA for L2 needs at least 5 states. L,-(a2nl n 2} with the set(a) as the alphabet. b) Problem 2 a) Prove that L3 is decidable. The alphabet is {a,b) L,-{ | M is a DFA such that no sentence in L(M) contains aaba as a substring) b) Use the minimum state lemma to prove that the language L4 with the set fa,b.c) as the alphabet is not regular L,-(an x x 1 n > 0 and x e (b+c)* } (b+c)*