Section outline

  • October 11th, Wednesday (12:30-14:30)

    Finite state automata

    • Construction: Conversion of a NFA into a DFA through lazy evaluation
    • Theorem: correctness of the subset construction
    • Theorem: equivalence of DFA and NFA
    • Theorem: Exponential growth of the set of states, worst case example
    • Partial DFA
    • Example on the subset construction for NFA

    Exercises

    • Let \(\#_a(w)\) be the number of occurrences of symbol \(a\) in string \(w\). Given two strings \(x\) and \(w\) over some alphabet \(\Sigma\), \(x\) is a prefix of \(w\) if we can write \(w = xv\) for some \(v \in \Sigma^\ast\). Define a DFA that accepts the language \( L = \{ w \; | \; w \in \{a,b\}^\ast, \) for every prefix \(x\) of \(w\) we have \( \#_b(x) \leq \#_a(x) \leq \#_b(x)+2 \} \) (exercise 2, 3rd question, final exam of 2019/09/13)

    References

    • Hopcroft et al., chapter 2