Notes - Logic and Proof MT24, Regular languages
-
[[Course - Logic and Proof MT24]]U
- Properties used in proof of decidability of:
- [[Notes - Logic and Proof MT24, Presburger arithmetic]]U
- See also:
- [[Course - Models of Computation MT23]]U
- [[Notes - Models of Computation MT23, DFAs]]U
- [[Notes - Models of Computation MT23, NFAs]]U
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^\ast(\sigma_1) \cdots f^\ast(\sigma_m)\]
In this context, can @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$