Prove by induction that if w is a string of a Solution the string contains k ( p

Question

Explanation / Answer

the string contains k ( positive and even) number of a's such that the language is (b*ab*ab*) so, when k= 2, the language is (b*ab*ab*) having two a'2 and so, W is the the language while it satisfies the grammar (N,T,R,S) N={a,b,*,S},T={a,b}, S is the start, so, P={ S--> b, S--> b*a, A--> ab} suppose for k=m, the format given satisfies the grammar of the language. i.e. (b*ab*ab*...*ab) where there are m even number of a's and so, in the required format. when k = m+2, we have to extend two more ab's in the same format. i.e. (b*ab*ab*...*ab*ab*ab) where there are m+2 a's. observe that whenever m is even, m+2 is even. ( m = 2p ==> m+2 = 2(p+1) is even) so, there are even number of a's and the format satisfies the grammar conditions. therefore, it is a language. so, whenever P(m) holds, P(m+2) also holds. thus, by the principle of mathematical induction, the given format is a language.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.