Definition A formal language L:Σ∗→Prop is just a subset of finite strings in an alphabet Σ:Set. Decidability We say that L is decidable if there is a computational function that can decide membership in L. Kinds of languages Regular Language Context-Free Language