Teorema: Ogni espressione regolare può essere convertita nell’automa deterministico a stati finiti (DFA) che riconosce il linguaggio che essa descrive e viceversa. Quindi un linguaggio è regolare se e solo se esiste una regex che lo descrive.
todo pag. 67
Primo passo
Data , voglio costruire un automa deterministico a stati finiti (DFA) o un automa non deterministico a stati finiti (NFA) tale che .
Usiamo la ricorsione:
Per induzione,
todo continua
Secondo passo
Da definiamo un GNFA equivalente… todo continua
Definiamo il Generic Non deterministic Finite state Automaton (GNFA) canonico