1. Recognition
2. Finite Languages
Is a finite set of words. Can use a recognition algorithm to compare the input word with each. Not efficient for larger languages.
3. Regular Languages
Definition: Regular Language
- It is the empty language, {}, or the language consisting of the empty word, {epsilon}.
- It is a language of the form {a} for some a part of Sigma.
- It is a language built using the union, concatenation or Kleene star of two regular languages
DFA
Use state diagrams to represent regular languages. For each state, there is only one transition on a given symbol, incorrect to define transitions from a state on the same symbol to more than one state. = there is no choice
DFAs are used in the Scanning stage of a compiler, where the input is a sequence of charactes representing the program and the output is a sequence of tokens.
Compilers will often tokenize using a simpler DFA and then programmatically weed out invaid words.
NFA
4. Scanning
Recognition is no the same as scanning. While recognition determines whether a string is a single word in the language, scanning is the process of taking a string and breaking it into words that are in the language.