Tutorial: Regular Languages

2025-05-21

1 CSC 236 Tutorial 11

2 Regular

Show the following languages are regular.

Use any means to show that the following languages are regular. Hint: using closure properties often give you quicker proofs.

  1. \(\{w: w \text{ ends with 01 and doesn't contain 111 as a substring}\}\)

  2. \(\{w: w \text{ never has more than five 1s in a row}\}\)

  3. \(\{w: w \text{ has length divisible by 4 and the number of 1s is divisible by 3}\}\)

  4. \(\{w: w \text{ has an even number of 1s or an even number of 0s but not both}\}\)

Solution

Sketch.

  1. Write the language as \[ \{w: w \text{ ends with 01}\} \cap \overline{\{ w: w \text{ contains 111 as a substring}\}}. \] The first language is matched by the regex \(\Sigma^*01\), and the second is matched by \(\Sigma^*111\Sigma^*\). Then, since regular languages are closed under intersection and negation, the original language is regular.

  2. \(\Sigma^*111111\Sigma^*\) is a regular expression for has more five 1s in a row. Regular languages are closed under negation, so done.

  3. \((\Sigma\Sigma\Sigma\Sigma)^*\) is \(w\) has length divisible by \(4\), and \((0^*10^*10^*10^*)^*\) is regex for the number of 1s is divisible by 3. Regular languages are closed under intersections.

  4. We showed previously has an even number of 1s, and even number of 0s are both regular. The language in the question is the symmetric difference of those two (and we showed that the symmetric difference of regular languages is regular.)

3 Dropout1

3.1

Let \(A\) be any language, define \(\mathrm{Dropout}(A)\) to be the language consisting of all strings that can be obtained by removing one symbol from \(A\).

Show that the regular languages are closed under \(\mathrm{Dropout}\). I.e., if \(A\) is regular, then so is \(\mathrm{Dropout}(A)\).

A correct construction of a DFA/NFA/Regex is good enough - no need to formally prove that the language of your construction is equal to \(\mathrm{Dropout}(A)\).

Solution

Let \(M\) be a DFA for \(A\). We’ll construct an NFA, \(N\) for \(\mathrm{Dropout}(A)\).

\(N\) will have two copies of \(M\), \(M_1\) and \(M_2\). We will start by running the string on \(M_1\) until we decide to skip a letter and continue running the DFA on \(M_2\).

A little more detail:

  • Since we must skip a letter, make all the states in \(M_1\) rejecting.

  • For each transition \((q, \sigma) \to q'\), add an \(\epsilon\) transition for \(M_1\)’s copy of \(q\) to \(M_2\)’s copy of \(q'\). This allows us to choose to skip a letter and forces us to move to \(M_2\) after the skip.

Footnotes

  1. Sipser, exercise 1.43↩︎