• Regular. It does not require any memory other than a state to parse it.
• is completely equivalent to this. And so is Finite State
  • {{video https://youtu.be/528Jc3q86F8?si=cZJ0jL_PZP4AtJBf}}
• The production rule: \(A \to a\) and \(A\to aB\)
• ./web.html#orgbdead17 and XML notations comes from this.

Example:

<identifier> ::= <letter><tail>
<letter> ::= [A-Za-z]
<tail> ::= [A-Za-z0-9_]<tail>
<tail> ::= [;]

• Context-free
• Non-deterministic pushdown automaton
• \(A\to \alpha\)

• Context-sensitive
• Linear-bounded non-deterministic Turing machine
• \(\alpha A\beta \to \alpha\gamma\beta\)

• Recursively enumerable
• \(\gamma\to \alpha\) (\(\gamma\) non-empty)