CS213 Assignment 2-Morphisms Solution

The objects to be studied in this assignment are called morphisms. Suppose Σ is a finite set of characters, which we will assume is a subset of {a,b,c,d,e,f}. Then Σ∗ denotes the set of all sequences whose elements are these characters, that is, it is just the set of all strings, also called words, containing only the given set of characters.
A morphism f is a function f : Σ → Σ∗ that assigns to each character x ∈ Σ some word f(x) ∈ Σ∗. The morphism f can be extended to all words in Σ∗ by defining f(λ) = λ and f(w · x) = f(w) · f(x), for all words w ∈ Σ∗ and characters x ∈ Σ. Here λ is the empty word and · denotes concatenation.
Suppose f(a) also has a as the first character. Then consider the sequence of words a,f(a),...,fn(a),..., where f0(a) = a and fn(a) = f(fn−1(a)). It can be seen that fn−1(a) is a prefix of fn(a) for all n ≥ 1, and as n → ∞ this sequence approaches a fixed, possibly infinite, word called its limit.
You have to write a program to find some properties of this sequence.
1. Given a number n, find the length of fn(a).
2. Given a number i, find the character at index i in the limit, or equivalently, the character at index i of fn(a) for any n for which length of fn(a) is greater than i. The 0th character will always be a. It can be assumed that i is less than the length of the limit.
3. Given a word w, determine if it is substring of fn(a) for some n, and if so find the smallest such n. If not a substring for any n, output −1. If the word is a substring, find the smallest index in the limit at which it occurs as a substring.
4. Given a word w, determine if it is a subsequence of fn(a) for some n, and if so, find the smallest possible n. Again, output −1 if it is not a subsequence. If it is a subsequence, also output the length of the shortest prefix of the limit, such that w is a subsequence of the prefix.
Input/Output The first line of input will specify the number of characters k, where 1 ≤ k ≤ 6. It can be assumed that the characters are the first k characters in the sequence a,b,c,d,e,f. The next k lines will contain a string each, the ith line giving the value of f for the ith character. It can be assumed that the length of each string is at most 20. The next line will specify the number of test cases. Each test case, given in a separate line, will consist of one of the 4 operations defined above. The type of an operation is defined by one of the numbers 0,1,2,3, which will be given first on the line. If the operation is 0 or 1, it will be followed by a single non-negative integer n. If the operation is 0, the output should be the length of fn(a) and if the operation is 1, the output is the character at index n in the infinite sequence. It can be assumed the length of fn(a) will be at most 1018 for operation 0, and n will be at most 1018 for operation 1. If the operation is 2 or 3, this will be followed by a string of length at most 1000. If
1
the operation is 2, the output should be the smallest n such that the given string is a substring of fn(a), followed by the smallest index at which it occurs, and −1 if it not a substring. For operation 3, the output should be the smallest n such that the given string is a subsequence of fn(a), and the length of the shortest prefix of fn(a) of which it is a
subsequence, and −1 if there is no such n. The output of each test case must be printed on a separate line, in the same order as the input.
Homework: Prove that the Fibonacci word is cube-free, that is, it does not contain a substring of the form v · v · v for any string v. Prove that the Thue-Morse word is overlap-free, that is, it does not contain two overlapping occurrences of the same string. This implies it is cube-free. Construct a morphism with 3 letters such that the generated word is square-free.
Submission: Submit a single file named RollNo 2.cpp .
2