20  Exercises

1. For each of the automata below, eliminate the state “E” by:
   1. first identify all the arrows pointing into “E” and out of “E”
   2. replace each path \(A \xrightarrow{u} E \xrightarrow{v} B\) by \(A \xrightarrow{ul^*v} B\) where \(l\) is the loop at “E”.

stateDiagram
    direction LR

    [*] --> E
    E --> A : 0
    E --> B : 1
    A --> A : 0
    B --> A : 1

Figure 20.1: FSA for exercise 1

stateDiagram
    direction LR

    [*] --> A
    A --> A : 0
    A --> E : 1
    E --> E : 0
    E --> B : 1
    B --> E : 1
    B --> [*]

Figure 20.2: FSA for exercise 1

stateDiagram
    direction LR

    [*] --> A
    A --> E : 0
    B --> E : 0
    A --> B : 1
    E --> E : 1
    E --> A : 0

Figure 20.3: FSA for exercise 1

2. Write the described language using \(+, \cdot\) (concatenation) and \(^*\) (Kleene star or plus)
   1. \(\{\varepsilon, 0, 1, 11, 111, 1111, \cdots\}\)
   2. Strings of \(0\)s with at least two \(0\)s
   3. Strings of \(0\)s with an even number of \(0\)s
   4. Strings of \(0\)s with an odd number of \(0\)s

Hint

1. How does this compare to \(\{\varepsilon, 1, 11, 111, 1111, \dots\} = 1^*\)?
2. Set the two \(0\)s aside first (compare to \(a^+ = aa^*\))
3. Think in terms of repeating \(00\)
4. Combine ideas from b. and c.

3. Consider the language \(L = 0^*(11)^*\).
   1. List all words in \(L\) of length \(\le 6\).
   2. Let \(a_n\) be the number of words in \(L\) of length \(n\). Using part a, guess a formula for \(a_n\) (which may depend on whether \(n\) is even or odd).
   3. Can you prove your formula?

Hint

In words: \(L\) describes languages with some number of \(0\)s followed by an even number of \(1\)s. So for instance, if \(n = 9\), the possible number of \(1\)s is \(0, 2, 4, 6, 8\) and there would be \(5\) possible strings. The formula should look something like \(n/2\) or \((n + 1)/2\).

4. Consider a tiling problem where we tile a \(2 \times n\) grid using horizontal or vertical dominos (\(1 \times 2\) or \(2 \times 1\)) or a \(2 \times 2\) square. Let \(\Sigma = \{V, H, S\}\) where \(V\) represents a vertical domino, \(H\) represents a horizontal domino, and \(S\) represents a square. A tiling can be described by the language \(L = \Sigma^*\).
   1. Let \(f\) be the weight function describing the width. So \(f(V) = 1, f(H) = f(S) = 2\). What is the generating function for \(\Sigma\)?
   2. What is the generating function for \(L = \Sigma^*\)?
   3. Using SageMath’s Taylor series method, compute the number of such tilings of a \(2 \times 10\) grid. Note: you have to write 2*x rather than 2x in SageMath.
   4. Using our techniques from recursion, what is a recursive formula for the number of tilings \(t_n\)? Compare this to the denominator of your OGF like in Section 18.4.

Hint

The generating function of \(\Sigma\) is \[ \Phi_\Sigma = \sum_{w \in \Sigma} x^{f(w)} = x^{f(V)} + x^{f(H)} + x^{f(S)}. \] For b. use Theorem 16.1.

For d. use the fact that a tiling of length \(n\) is either: * a tiling of length \(n - 1\) followed by a vertical domino, * a tiling of length \(n - 2\) followed by either a pair of horizontal dominoes or a square (so \(2\) options).

5. Draw a finite automata for:
   1. the language \(0^*(11)^*\)
   2. the language \((0 + 11)^*\)

The automata in these notes were drawn using the Mermaid Javascript library. You may wish to copy the following code to mermaid.live and modify it to create the FSA you need.

stateDiagram-v2
    direction LR
    classDef accept stroke-width:5px
    [*] --> 0
    0 --> 0 : 0
    0 --> 1 : 1
    1 --> 11 : 1
    11 --> 11 : 1

    class 0, 11 accept

Hint

The FSA for part a should require only slight modification of the sample Mermaid diagram. Likewise, part b should require only slight modification from part a.

6. Take the FSA from the previous question and perform state elimination to check if you recover the regular expression you started with. Remember to add in a termination state before you start eliminating.

Hint

Use the \(ab^*c\) formula described in Section 17.3.1 on each path \(A \to S \to B\) to eliminate \(S\).

7. In Example 8.18 of Keller and Trotter’s book, they show using exponential generating functions that the number of ternary strings with an even number of \(0\)s is \((3^n + 1)/2\). In this exercise, we will get this answer using ordinary generating functions.
   1. Draw a FSA for this language (you can do it in two states, not including the start and end).
   2. Perform state elimination to obtain a regular expression.
   3. Convert that regular expression to an OGF.
   4. Using SageMath, find a partial fraction decomposition for the OGF.
   5. Verify that the Taylor series is \(\sum \frac{3^n + 1}{2} x^n\).

Hint

1. The start state will represent an even number of \(0\)s seen so far and another state will represent an odd number.
2. Eliminate the odd state using the elimination rule: in(loop)*out.
3. Replace \(0, 1, 2\) by \(x^1\) since each of those characters has length \(1\).
4. Don’t forget to use 2*x rather than 2x.
5. Use the formula \(\frac{a}{1 - r} = \sum ar^n\).

Solutions

stateDiagram
    direction LR

    [*] --> E
    E --> A : 0
    E --> B : 1

stateDiagram
    direction LR

    [*] --> A : 0
    [*] --> B : 1
    A --> A : 0
    B --> A : 1

stateDiagram
    direction LR

    A --> E : 1
    E --> E : 0
    E --> Bout : 1
    Bin --> E : 1

stateDiagram
    direction LR

    [*] --> A
    A --> A : 0
    A --> B : 10*1
    B --> B : 10*1
    B --> [*]

stateDiagram
    direction LR

    Ain --> E : 0
    B --> E : 0
    E --> E : 1
    E --> Aout : 0

stateDiagram
    direction LR

    [*] --> A
    A --> A : 01*0
    B --> A : 01*0
    A --> B : 1

2. 1. \(0 + 1^*\)
   2. \(000^*\) or \(00^+\)
   3. \((00)^*\)
   4. \(0(00)^*\)