Formal Language

• Definition: A formal language over an Alphabet $\sum$ is any Subset of ${\sum }^{\ast }$.
• Meaning: It’s just a set of strings built from the alphabet.
• Examples:
  • Over $\sum =\{a,b\}$:
    • $L_1=a^n{b}^n|n\ge 0$
    • $L_2=\{w\in {\sum }^{\ast }\mid w\mathrm{has}\mathrm{an}\mathrm{even}\mathrm{number}\mathrm{of}a\}$
• Note: Really, the kinds of formal languages we’re interested in are the ones that can be produced by some kind of rule.