Logic and Proof MT24, Regular languages
- Course - Logic and Proof MT24U
- Properties used in proof of decidability of:
- Notes - Logic and Proof MT24, Presburger arithmeticU
- See also:
- Course - Models of Computation MT23U
- Notes - Models of Computation MT23, DFAsU
- Notes - Models of Computation MT23, NFAsU
The following closure properties are useful in showing certain theories are decidable.
Flashcards
Suppose $f : \Sigma \to \Gamma$ is a map between alphabets, and $f^\ast : \Sigma^\ast \to \Gamma^\ast$ is its extension to strings by
\[f^\ast(\sigma _ 1 \cdots \sigma _ m) = f(\sigma _ 1) \cdots f(\sigma _ m)\]
In this context, @state two closure properties of regular languages.
- If $L$ is regular, then $f^\ast(L)$ is also regular, and can be efficiently constructed from an NFA for $L$
- If $L$ is regular, then $(f^\ast)^{-1}(L)$ is also regular, and can also be efficiently constructed from an NFA for $L$