Grammar
Chomsky generative grammar
Chomsky generative grammar $G$ is a system used for generating strings over some alphabet. It is defined by a 4tuple:
$G = (N, \Sigma, P, S)$Where:

$N$ is a finite set of nonterminal symbols. These symbols are never present in the strings of the language, but are used in the production rules to generate those strings.

$\Sigma$ is a finite set of terminal symbols. These symbols appear in the strings generated by the grammar and are distinct from the nonterminals, i.e., $N \cap \Sigma = \emptyset$. The symbols in $\Sigma$ form the alphabet of the language generated by the grammar.

$P$ is a finite set of production rules. Each production rule is of the form: $\alpha \rightarrow \beta$ Where $\alpha$ is a string of symbols that contains at least one nonterminal (i.e., $\alpha \in (N \cup \Sigma)^+$ and $\alpha$ contains at least one element from $N$), and $\beta$ is a string of symbols from $N \cup \Sigma$, i.e., $\beta \in (N \cup \Sigma)^*$.

$S$ is the start symbol, where $S \in N$. This is the symbol from which derivation or string generation starts.
A grammar specifies how to construct valid strings of the language. A string is considered part of the language if there exists some sequence of production rule applications (a derivation) that starts with the start symbol $S$ and results in that string.
Chomsky hierarchy
The Chomsky hierarchy classifies grammars into four levels based on their generative power:

Type 0  Recursively Enumerable (RE) Grammar
 Production Rules: $\alpha \rightarrow \beta$ where $\alpha, \beta \in (N \cup \Sigma)^+$ and $\alpha \leq \beta$
 Language: Recursively Enumerable Language
 Recognized by: Turing Machine

Type 1  ContextSensitive Grammar (CSG)
 Production Rules: $\alpha \rightarrow \beta$ where $\alpha, \beta \in (N \cup \Sigma)^+$ and $\alpha \leq \beta$
 Language: ContextSensitive Language (CSL)
 Recognized by: Linear Bounded Automaton (LBA)

Type 2  ContextFree Grammar (CFG)
 Production Rules: $A \rightarrow \beta$ where $A \in N$ and $\beta \in (N \cup \Sigma)^*$
 Language: ContextFree Language (CFL)
 Recognized by: Pushdown Automaton (PDA)

Type 3  Regular Grammar
 Production Rules:
 $A \rightarrow aB$ or $A \rightarrow a$ or $A \rightarrow \epsilon$ for rightlinear regular grammars.
 $A \rightarrow Ba$ or $A \rightarrow a$ or $A \rightarrow \epsilon$ for leftlinear regular grammars.
 Language: Regular Language
 Recognized by: Finite Automaton (either Deterministic (DFA) or Nondeterministic (FA))
 Production Rules:
However, this is a classical hierarchy proposed by Chomsky in 1956 in his paper “Three Models for the Description of Language.” Since then, it has been extended to capture more nuances.
Extended Chomsky hierarchy
 Linear grammar or Linear ContextFree grammar
 Is a ContextFree Grammar that has at most one nonterminal in the righthand side of each of its productions
 Examples: $A \rightarrow aB$, $A \rightarrow Ba$, $A \rightarrow aBa$
 RightLinear grammar
 Examples: $A \rightarrow aB$ or $A \rightarrow a$ or $A \rightarrow \epsilon$
 LeftLinear grammar
 Examples: $A \rightarrow Ba$ or $A \rightarrow a$ or $A \rightarrow \epsilon$
 Deterministic Context Free
 A language is deterministic contextfree (DCF) iff accepted by a determensitic pushdown automaton (DPDA)
 Example: “balanced” language
 Closed under negation?
 (Nondeterministic) Context Free
 A language is contextfree (CF) iff accepted by a (nondetermensitic) pushdown automaton (PDA)
 Example: set of all palindromes $\{ ww^R  w \in \Sigma^* \}$
 Indexed language
 A language is indexed iff accepted by a nested stack automaton (NSA)
 A language is indexed iff produced by a indexed grammar ↗
 Contextsensitive language
 A language is contextsensitive iff accepted by a nondetermensitic TM with linearly bounded memory (LBA)
 A language is contextsensitive iff generated by a contextsensitive grammar
 Closed under negation?