效鼎 RE to e-NFA:Induction 3-Closure E E For E E For E* .16
16 RE to ε-NFA: Induction 3 – Closure For E For E* ε ε ε ε
效绵鼎 DFA-to-RE ■ A strange sort of induction. ■ States of the DFA are named 1,2,...,n. ■ Induction is on k,the maximum state number we are allowed to traverse along a path .17
17 DFA-to-RE ◼ A strange sort of induction. ◼ States of the DFA are named 1,2,…,n. ◼ Induction is on k, the maximum state number we are allowed to traverse along a path
效绵鼎 k-Paths A k-path is a path through the graph of the DFA that goes through no state numbered higher than k Endpoints are not restricted;they can be any state. n-paths are unrestricted. RE is the union of RE's for the n-paths from the start state to each final state. .18
18 k-Paths ◼ A k-path is a path through the graph of the DFA that goes through no state numbered higher than k. ◼ Endpoints are not restricted; they can be any state. ◼ n-paths are unrestricted. ◼ RE is the union of RE’s for the n-paths from the start state to each final state
效绵鼎 Example:k-Paths 1 0-paths from 2 to 3: 1 2 RE for labels =0. 0 0 1 1 1-paths from 2 to 3: 3 RE for labels=0+11. 2-paths from 2 to 3: RE for labels (10)*0+1(01)*1 3-paths from 2 to 3: RE for labels ? .19
19 Example: k-Paths 1 3 2 0 0 0 1 1 1 0-paths from 2 to 3: RE for labels = 0. 1-paths from 2 to 3: RE for labels = 0+11. 2-paths from 2 to 3: RE for labels = (10)*0+1(01)*1 3-paths from 2 to 3: RE for labels = ??
效绵鼎 DFA-to-RE Basis:k=0;only arcs or a node by itself. ◆ Induction:construct RE's for paths allowed to pass through state k from paths allowed only up to k-1. .20
20 DFA-to-RE ◼ Basis: k = 0; only arcs or a node by itself. ◼ Induction: construct RE’s for paths allowed to pass through state k from paths allowed only up to k-1