Section outline

  • October 18th, Friday (08:30-10:30)

    Regular expressions

    • Translation of a DFA into a regular expression: state elimination construction
    • Example of the state elimination construction
    • Translation of a regular expression into an \(\varepsilon\)-NFA
    • Example
    • Algebraic laws for regular expressions

    Exercise

    • Given two strings \(x\) and \(w\) over some alphabet \(\Sigma\), \(x\) is an infix of \(w\) if we can write \(w = uxv\) for \(u, v \in \Sigma^\ast\). We define \(\mathit{Infx}(w)\) as the set of all infixes of \(w\). For a language \(L\), we define \(\mathit{Infx}(L) = \{ x \mid w \in L, x \in \mathit{Infx}(w)\}\). Prove that if \(L\) is a regular language, then \(\mathit{Infx}(L)\) is also a regular language.

    References

    • Hopcroft et al., chapter 3