Computational power wise, DFA < CFG < TM
<aside> <img src="/icons/light-bulb_blue.svg" alt="/icons/light-bulb_blue.svg" width="40px" /> Context-Free Grammars (CFGs) $G = (V, \Sigma, R, S)$ (Variables, Alphabet terminals, Rules, Start Variables)
</aside>
$\Sigma$ is disjoint from variables
A rule is a substitution mechanism. Like replacing a variable to $(\Sigma\cup V)^*$
Example:
$G_1:(\{A\}, \{0,1\},R,A)$
Rules:
A → 0A1
A → $\epsilon$ “empty string”
<aside> <img src="/icons/light-bulb_blue.svg" alt="/icons/light-bulb_blue.svg" width="40px" /> Derivations $\alpha \in (\Sigma\cup V)^, \beta \in (\Sigma\cup V)^$ We say $\alpha \Rightarrow_G\beta$ if we can get $\beta$ by replacing a variable in $\alpha$ using a rule from R
</aside>
In the example $G_1$ above:
$A \Rightarrow_G 0A1$, $0A \Rightarrow_G 00A1$, $AA0 \Rightarrow_G 0A1A0$, $AA0 \Rightarrow_G A0A10$
<aside> <img src="/icons/light-bulb_orange.svg" alt="/icons/light-bulb_orange.svg" width="40px" /> We say $\alpha \Rightarrow_G^* \beta$ if there exist a chain of derivations to get $\beta$ from $\alpha$ In other words, there exist some $\alpha_1, \alpha_2, \dots, \alpha_{l-1}$ such that $\alpha_1 \Rightarrow_G \alpha_2 \Rightarrow_G\alpha_3\Rightarrow_G...\Rightarrow_G \alpha_{l-1} \Rightarrow_G\beta$
</aside>
Still in the example $G_1$ above:
$A \Rightarrow_G^* 00A11$, $AA \Rightarrow_G^* 0001110A1$
<aside> <img src="/icons/light-bulb_blue.svg" alt="/icons/light-bulb_blue.svg" width="40px" /> If G is a grammar, $x\in \Sigma^$ is matched to G is $S \Rightarrow_G^ x$, then $L_G = \{x\in\Sigma^* : x \text{ matches G}\}$ $F_G:\Sigma^*\to\{0,1\}, F_G(x) = \begin{cases}1 &\text{if x matches G}\\0 & \text{otherwise}\end{cases}$
</aside>
“Language generated by grammar G” is $L_G$
Definition
A function $f: \Sigma^*\to\{0,1\}$ is context-free if there exist a grammar G such that $f(x) = F_G(x) \forall x$
What’s the language generated by the $G_1$ above?
$L_G = \{0^n1^n: n\ge 0\}$
Every time we apply rule A → we add 0 to left of A and 1 to right of