consider \"alphabet\" consisting of the two letters a and b , together with the
ID: 3075808 • Letter: C
Question
consider "alphabet" consisting of the two letters a and b , together with the following rules for creating new "words" from old ones. The rules may be applied in any order. Use one rule at a time to create new words from old ones. RULE 1: Double the current word . ( for example, if bba is a word, then bbabba is a word.) RULE 2: Erase bb from the current word. ( for example babba is a word, then baa is a word.) RULE 3: Replace aaa in the current word by b. (for example, if aaaba is a word, then bba is a word ) RULE 4: If the last letter of the current word is a, then b at the right end of the current word. ( For example, if aba is a word, then abab is a word ) a) derive all the possible words that can be obtained in exactly three steps by repeatedly applying the above rules to the initial word a.Explanation / Answer
The only two rules that we can start with are 1 and 4, so we'll try both of those options. Start with rule 1: aa Now we have two options, 1 or 4, which give: aaaa or aab With aaaa, we can do rules 1, 3 (on either the first three a's or the last three a's), or 4, which give: aaaaaaaa or ab or ba or aaaab And we've used three steps. Start with rule 4: ab Now the only rule we can do is 1, so we get: abab We can still only do rule 1, so we get: abababab So the only five words that you can get after three steps are aaaaaaaa, ab, ba, aaaab, and abababab.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.