Question

(a)  Let S = {a, b, ab, aba}. How many different factorizations are there of (ab)¹¹ ? It is not enough to give me a number. You need to prove (i.e., justify or explain very carefully) that your number is correct. 

This is for an automated languages course

Answer 1

Solutions for the problem is provided below, please comment if any doubts:

Answer: 22

Explanation:

• (ab)¹¹ = ababababababababababab
• S= {a, b, ab, aba}
• The number of ways the strings of S can be used to generate (ab)¹¹ is the number of factorizations.
• We need to check every possibility using the four strings in S.
• 1: There is a possibility of making (ab)¹¹ by using only “a” and “b” 11 times each.
• 1: With only using eleven “ab” there is a possibility.
• Now take the combination of the strings:
• 10: Using “ab”, “a”, and “b”.
  • 10 “ab” and one “a” and “b”.
  • 9 “ab” and rest “a” and “b”.
  • Like 10 combinations;
• 5: Using “aba”, “b” and “ab”.
  • Five “aba”, five “b” and an “ab” will constitute (ab)¹¹.
  • Four “aba”, four “b” and three “ab” will give (ab)¹¹.
  • Three “aba”, three “b” and five “ab”.
  • Two and one “aba” combination is also there.
• 5: Using “aba”,“a” and “b”.
  • Five “aba”, six “b” and an “a” will constitute (ab)¹¹.
  • Four “aba”, seven “b” and three “a” will give (ab)¹¹.
  • Three, Two and one “aba”, “a” and “b” combination is also there.
• Now total different factorizations are: 10+5+5+1+1=22.