consider \"alphabet\" consisting of the two letters a and b , together with the

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 )

d) prove: If a is a word, then bbab is a word

Explanation / Answer

Using rule 1 repeatedly, we can get: a --> aa --> aaaa --> aaaaaaaa --> aaaaaaaaaaaaaaaa Now we use rule 3 five times to get: bbbbab Then we can use rule 2 to erase the first two b's to get: bbab So if a is a word, then bbab is a word.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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