=========== Part A ===========
1. Prove using induction that |x.y| = |x| + |y| where . indicates the concatenation operator.
2. Formally define the #(a,s) operation where a is a symbol, s is a string and the operation returns the number of occurrences of a in s.
3*. Prove that #(a,s.t) = #(a,s) + #(a,t).
=========== Part B ===========
4. Define a languge L such that complement of L is { w : w contains neither the substrings ab nor ba }.
5. Use (4) to design a DFA for L.
6*. Design a DFA for { w : w is any string except 11 and 111} over the alphabet {0,1}.