Consider the following game: you are given a sequence of the letters A and B, and...

 

Transcribed Image Text:

Consider the following game: you are given a sequence of the letters A and B, and you are given the following replacement rules that allow you to replace some combinations of letters with different combinations of letters. (1) AA can be removed or inserted anywhere in the sequence. (ii) BBB can be removed or inserted anywhere in the sequence. (iii) ABA can be replaced with B, and B can be replaced with ABA. As an example of a round of play, consider starting with the word BABB. Using (1), we can insert AA at the beginning of the sequence to get AABABB. Then using (3), we can replace ABA in the middle of the sequence with B to get ABBB. Then using (2), we can remove BBB to get just A. (a) Show that rules (i), (ii) and (iii) allow you to transform AB to B.A. (b) Show that you cannot transform A to B using rules (i), (ii), and (iii). (c) Use part (a) to show that rules (i), (ii) and (iii) allow any finite sequence of 'A's and 'B's to be transformed to one of the following A, B, AB, BB, ABB or, where is the empty word; that is, is a word with no letters. (d) Consider the situation where (iii) is replaced by (iii*) ABA can be replaced with BB, and BB can be replaced with ABA. Show that (i), (ii), and (iii*) do not allow you to transform AB to BA. (e) Show that even though AB cannot be replaced by BA, any finite sequence of 'A's and 'B's can still be transformed to one of the following A, B, AB, BB, ABB or, with rules (i), (ii) and (iii*). Consider the following game: you are given a sequence of the letters A and B, and you are given the following replacement rules that allow you to replace some combinations of letters with different combinations of letters. (1) AA can be removed or inserted anywhere in the sequence. (ii) BBB can be removed or inserted anywhere in the sequence. (iii) ABA can be replaced with B, and B can be replaced with ABA. As an example of a round of play, consider starting with the word BABB. Using (1), we can insert AA at the beginning of the sequence to get AABABB. Then using (3), we can replace ABA in the middle of the sequence with B to get ABBB. Then using (2), we can remove BBB to get just A. (a) Show that rules (i), (ii) and (iii) allow you to transform AB to B.A. (b) Show that you cannot transform A to B using rules (i), (ii), and (iii). (c) Use part (a) to show that rules (i), (ii) and (iii) allow any finite sequence of 'A's and 'B's to be transformed to one of the following A, B, AB, BB, ABB or, where is the empty word; that is, is a word with no letters. (d) Consider the situation where (iii) is replaced by (iii*) ABA can be replaced with BB, and BB can be replaced with ABA. Show that (i), (ii), and (iii*) do not allow you to transform AB to BA. (e) Show that even though AB cannot be replaced by BA, any finite sequence of 'A's and 'B's can still be transformed to one of the following A, B, AB, BB, ABB or, with rules (i), (ii) and (iii*).

Answer rating: 100% (QA)

Lets go through each part of the question separately a Show that rules i ii and iii allow you to transform AB to B4 Using the given rules we can perform the following transformations 1 Start with AB 2 ... View the full answer