# 自動機與形式語言
[TOC]

## Lesson 1(Regular Languages)

### Parameters
__Deterministic finite state automata__ _DFA_ $\mathcal{A}=\langle \Sigma, Q, q_0, F, \delta \rangle$
+ $\Sigma$ is the alphabet.
+ $Q$ is a _finite_ set of states.
+ $q_0\in Q$ is the initial state.
+ $F \subseteq Q$ is the set of accepting states.
+ $\delta:Q\times \Sigma \rightarrow Q$ is the transition function.

__Nondeterministic finite state automata__ _NFA_ $\mathcal{A}=\langle \Sigma, Q, q_0, F, \delta \rangle$
+ $\Sigma$ is the alphabet.
+ $Q$ is a _finite_ set of states.
+ $q_0\in Q$ is the initial state.
+ $F \subseteq Q$ is the set of accepting states.
+ $\delta \subseteq Q\times \Sigma \times Q$ is the transition function.

### Theorem 1.3
> _Regular languages are closed under boolean operations, i.e., intersection, union, and complementation. More formally, it can be stated as follows._
> + For every _DFA_ $\mathcal{A}$, there is a _DFA_ $\mathcal{B}$ such that $L(\mathcal{B}) = \Sigma^{*} − L(\mathcal{A})$.
> + For every two _DFA_ $\mathcal{A_1}$ and $\mathcal{A_2}$, there is a _DFA_ $\mathcal{B}$ such that $L(\mathcal{B}) = L(\mathcal{A_1}) \cap L(\mathcal{A_2})$.
> + For every two _DFA_ $\mathcal{A_1}$ and $\mathcal{A_2}$, there is a _DFA_ $\mathcal{B}$ such that $L(\mathcal{B}) = L(\mathcal{A_1}) \cup L(\mathcal{A_2})$.

- #### Proof (statement 1)
For $\mathcal{A}=\langle\Sigma, Q, q_{0}, F, \delta\rangle$
Define
+ $Q_\mathcal{B}=Q$
+ $q_{0,\mathcal{B}}=q_{0}$
+ $F_{\mathcal{B}}=Q-F$
+ $\delta_{\mathcal{B}}=\delta$

Then $\mathcal{B}=\langle\Sigma, Q_{\mathcal{B}}, q_{0, \mathcal{B}}, F_{\mathcal{B}}, \delta_{\mathcal{B}}\rangle$ is a _DFA_ which satisfies $L(\mathcal{B}) = \Sigma^{*} − L(\mathcal{A})$.

- #### Proof (statement 2)
For $\mathcal{A_1}=\langle\Sigma, Q_1, q_{0, 1}, F_1, \delta_1\rangle$, $\mathcal{A_2}=\langle\Sigma, Q_2, q_{0, 2}, F_2, \delta_2\rangle$
Define
+ $Q=Q_1\times Q_2$
+ $q_{0}=(q_{0, 1}, q_{0, 2})$
+ $F=F_1\times F_2$
+ $\delta:Q\times\Sigma\rightarrow Q \mbox{, where } \delta((q_1, q_2), a)=(\delta_1(q_1, a), \delta_2(q_2, a))$

Then $\mathcal{B}=\langle\Sigma, Q, q_{0}, F, \delta\rangle$ is a _DFA_ which satisfies $L(\mathcal{B}) = L(\mathcal{A_1}) \cap L(\mathcal{A_2})$.

For input word $w=a_{1}a_{2}...a_{n}$

$L(\mathcal{B})\subseteq L(\mathcal{A_1})\cap L(\mathcal{A_2}):$
$\ \ \ \forall w\in L(\mathcal{B})$, By def
$\ \ \ q_0\ a_1\ q_1\ a_2 ...a_n\ q_n =\ \ (q_{0, 1}, q_{0, 2})\ a_1\ (q_{1, 1}, q_{1, 2})\ a_2 ...a_n\ (q_{n, 1}, q_{n, 2})$
$\ \ \ (q_{n, 1}, q_{n, 2})\in F_{1}\times F_2$
$\ \ \ \Rightarrow w\in L(\mathcal{A_1})\cap L(\mathcal{A_2})$

$L(\mathcal{A_1})\cap L(\mathcal{A_2})\subseteq L(\mathcal{B}):$
$\ \ \ \forall w\in L(\mathcal{A_1})\cap L(\mathcal{A_2})$
$\ \ \ q_{0, 1}\ a_1\ q_{1, 1}\ a_2 ...a_n\ q_{n, 1}$ is a run of $\mathcal{A_1}$ on $w$,
$\ \ \ q_{0, 2}\ a_1\ q_{1, 2}\ a_2 ...a_n\ q_{n, 1}$ is a run of $\mathcal{A_2}$ on $w$, than
$\ \ \ (q_{0, 1}, q_{0, 2})\ a_1\ (q_{1, 1}, q_{1, 2})\ a_2 ...a_n\ (q_{n, 1}, q_{n, 2})$ is a run of $\mathcal{B}$ on w
$\ \ \ \Rightarrow w\in L(\mathcal{B})$

### Theorem 1.5
> For every _NFA_ $\mathcal{A}$, there is a _DFA_ $\mathcal{B}$ such that $L(\mathcal{A}) = L(\mathcal{B})$.

- #### Proof
For $\mathcal{A}=\langle\Sigma, Q, q_{0}, F, \delta\rangle$
Define
+ $Q_\mathcal{B}=2^Q$
+ $q_{0,\mathcal{B}}=\{q_{0}\}$
+ $F_{\mathcal{B}}=\{S|S\subseteq Q\mbox{ and }S\cap F\neq \emptyset\}$
+ $\delta_{\mathcal{B}}:2^Q\times\Sigma\mbox{, where } \delta_{\mathcal{B}}(S, a) = \{p|p\in Q \mbox{ and there is }q\in S\mbox{ s.t. }(q, a, p)\}$

> each state of $\mathcal{B}$ is a set[color=RED]

Then $\mathcal{B}=\langle\Sigma, Q_{\mathcal{B}}, q_{0, \mathcal{B}}, F_{\mathcal{B}}, \delta_{\mathcal{B}}\rangle$ is a _DFA_ which satisfies $L(\mathcal{A}) = L(\mathcal{B})$.

### Number of regular language
> The set of all regular language is Countable

可以將所有 _NFA_ 依據state的數量排列，每個state數量可產生的 _NFA_ 的數量是有限的，而state的數量有可數無窮個，得證之

> There is a language that is __NOT__ regular

因為所有的language數量是不可數無窮個

### Pumping Lemma
> $\mathcal{A}=\langle \Sigma, Q, q_0, F, \delta \rangle$ is an NFA.Suppose there is a word $x\in L(\mathcal{A})$ such that $|x| \ge |Q|$. Then, the word $x$ can be divided into three parts $u,v,w$, i.e., $x = uvw$, such that $|v| \ge 1$ and for every positive integer $i \ge 0$, $uv^iw \in L(\mathcal{A})$.

表示至少一個state會被走超過一次，那麼相鄰的兩次便會形成一個環，多走或少走幾次環仍然會在$L(\mathcal{A})$之中

> 

::: info
__Technique__
To show a language that is not regular, find a word with length $n\ge|Q|$, and use pumping lemma with proof by contradiction.
> Example :
> Prove that $L = \{a^n b^n|\ n\ge 0\}$ is not regular, which means that $\forall \mathcal{A}, L(\mathcal{A}) \neq L$.
> Suppose $\mathcal{A}=\langle \Sigma, Q, q_0, F, \delta \rangle$ s.t. $L(\mathcal{A}) = L$.
>
> 
>
> Thus, $\forall \mathcal{A}, L(\mathcal{A}) \neq L$, Q.E.D.
:::

:::warning
## Converse of lemma not true
Let $L$ be a language.
Suppose there is integer $N\ge0$ s.t.
$\forall x, |x|\ge N$, there is $u, v, w$ s.t.
- $|v|\ge 1$
- $x=uvw$
- $uv^iw\in L,\ \forall i=0,1,2,...$

Then, $L$ is regular(???)
https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Converse_of_lemma_not_true
:::

### Regular expression (Regex)

> __Remind :__
> $L(\emptyset) = \emptyset$
> $L(\emptyset^*) = L(\emptyset)^* = \emptyset^0\cup\emptyset^1\cup\ldots\cup\ldots = \{\epsilon\}\cup\emptyset^1\cup\ldots\cup\ldots = \{\epsilon\}$

### Theorem 1.11
> For every _NFA_ $\mathcal{A}$, there is a regular expression $\alpha$ such that $L(\alpha) = L(\mathcal{A})$, and
> For every regular expression $\alpha$ over $\Sigma$, $L(\alpha)$ is a regular language.

- #### Proof by induction on $\alpha$(statement 1)
+ __Base case__ :
$\alpha = \emptyset, L(\alpha)=\emptyset$

$\alpha = a, L(\alpha) = \{a\}$
+ __Induction step__ :
By, I.H., $\mathcal{A}_{\beta}$ for $L(\beta)$ and $\mathcal{A}_{\gamma}$ for $L(\gamma)$

$\alpha = \beta\cdot\gamma$
By def, $L(\alpha)=L(\beta)\cdot L(\gamma)$

$\alpha = \beta\cup\gamma$
By def, $L(\alpha)=L(\beta)\cup L(\gamma)$

$\alpha = (\beta)^{*}$
By def, $L(\alpha)=L(\beta)^*$
:::warning
由於有可能出現以下狀況，使得原本還沒到終點的序列變得合法，因此不能直接將起點設為終點
:::

- #### Proof (statemant 2)
Let _NFA_ $\mathcal{A}=\langle\Sigma, Q, q_0, F, \delta\rangle$, without loss of gererality assume $Q = \{1, 2, \ldots, N\}$
For every $1\ge i, j\ge N$ and $0\ge k\ge N$, define
$\begin{eqnarray*}
L(i,j,k) & := &
\left\{
\begin{array}{l|l}
w &
\begin{array}{l}
\textrm{there is a run of}\ \mathcal{A} \ \textrm{on} \ w
\
\textrm{from state}\ i \ \textrm{to state}\ j
\\
\textrm{without passing any states} \ \geq k+1
\end{array}
\end{array}
\right\}
\end{eqnarray*}$
> state $i$ 到 state $j$ 間只經過編號 $\le k$ 的 state 所形成的 word 組成的 language

:::info
+ __Claim__
There is a regex $e$ such that $L(e) = L(i, j, k)$
- __Proof by induction on $k$__
Let $\Gamma_{i, j} = \{a|(i, a, j)\in\delta\}$
> a is a alphabet
- __Base case :__
if $k = 0, \Gamma_{i, j} = \emptyset\Rightarrow L(i, j, 0) = \emptyset$
$e = \left\{\begin{array}{ll}
\emptyset&\mbox{, if }i\neq j \\
\emptyset^{*}&\mbox{, if }i=j
\end{array}\right.$

if $k = 0, \Gamma_{i, j} =\{a_1, \ldots, a_t\}$
$e = \left\{\begin{array}{ll}
a_1\cup \ldots\cup a_t&\mbox{, if }i\neq j\\
a_1\cup \ldots\cup a_t\cup \emptyset&\mbox{, if }i=j
\end{array}\right.$

- __Induction step :__
$L(i, j, k+1) = \\
\ \
L(i, j, k)\cup(L(i, k+1, k)\cup L(k+1, k+1, k)^*\cup L(k+1, j, k))$
By the induction hypothesis, there are regexes that define each of $L(i, j, k), L(i, k + 1, k), L(k + 1, k + 1, k), \mbox{and } L(k + 1, j, k)$.
By the definition of regex, there is regex that define $L(i, j, k + 1)$.
:::

Note that
$$\begin{eqnarray*}
L(\mathcal{A}) & = &
\bigcup_{q_f \in F} \ L(q_0,q_f,N)
\end{eqnarray*}$$
By the claim above, for each $L(q_0,q_f,N)$, there is a regex that defines it. Thus, there is a regex for $L(\mathcal{A})$.

### Excercise
> For a language $L\subseteq\Sigma^*$,
> $$
> \mbox{half}(L) = \{w\ |\ \exists w'\mbox{, s.t. }|w|=|w'|\mbox{ and } ww'\in L\}
> $$
> Porve that if $L$ is regular than half$(L)$ is regular.

+ #### Proof
Let $\mathcal{A}=\langle\Sigma, Q, q_0, F, \delta_{\mathcal{A}}\rangle$ be a _DFA_ for $L$,
Define :
$$
Q_{\mathcal{B}} = \{(q, S)|q\in Q, S\subseteq Q\}\\
q_{0, \mathcal{B}} = (q_0, F)\\
F_{\mathcal{B}} = \{(q, S)|q\in S\}\\
\delta_{\mathcal{B}}((q, S), a) = (\delta_{\mathcal{A}}(q, a), T)\mbox{ where } T=\{r\in Q | \exists b\in\Sigma, s\in S\mbox{ s.t. } \delta_{\mathcal{A}}(r, b) = s\}
$$
Then $\mathcal{B} = \langle\Sigma, Q_\mathcal{B}, q_{0, \mathcal{B}}, F_\mathcal{B}, \delta_{\mathcal{B}}\rangle$ is a _DFA_ which satisfies $L(\mathcal{B})=\mbox{half}(L)$, thus, $\mbox{half}(L)$ is regular.

## Lesson 2(Context-free Languages)

### Parameters

__Context-free grammar__ _CFG_ $\mathcal{G} = \langle\Sigma, V, R, S\rangle$
+ $\Sigma$ is a finite set of symbols, called terminals.
+ $V$ is a finite set of variables, and $V\cap\Sigma=\emptyset$.
+ $R$ is a finite set of rules, where each rule is of the form:
$$A\rightarrow w$$
where $A\in V$ and $w\in (V\cup\Sigma)^*$.

+ $S$ is a special variable from $V$, called the start variable.

### Theorem 2.2
> Every regular language $L$ is a _CFL_.

- #### Proof by induction on the number of operators in a regular expression for $L$
+ __Base case :__
There has only one character $a$ in $L$ with no operator
We can just have a _CFL_ with a single transition: $S \rightarrow a$.
+ __Induction step:__
Take a language $L$ be represented by the regular expression $R$, such that $R$ has $k$ operators.
For every $i = 1, 2,\ldots$ assume that regular expression $R_i$ is produced by a _CFG_ with start symbol $S_i$
- __Union__
If $R = R_1\cup R_2$, then we create a new _CFG_ with start state $S$ and the production rule $S\rightarrow S_1|S_2$
- __Concatenation__
If $R = R_1R_2$, then we create a new _CFG_ with start state $S$ and the production rule $S \rightarrow S_1S_2$
- __KLeene star__
If $R = R_1^*$, then we create a new _CFG_ with start state $S$ and the production rule $S \rightarrow SS_1|\epsilon$

Therefore, since every regular expression has an equivalent _CFG_, every regular language is a CFL.

- #### Proof
Let $L$ be regular, _NFA_ $\mathcal{A}=\langle \Sigma, Q, q_0, F, \delta \rangle$ s.t. $L(\mathcal{A}) = L$
Define
+ $V = \{A_q|q\in Q\}$
+ $R : \left\{\begin{array}{ll}
\mbox{For every }(p, a, q)\in\delta, A_p\rightarrow aA_q, \\
\mbox{For every }q_f\in F, A_{q_f}\rightarrow \epsilon
\end{array}\right.$
+ $S = A_{q_0}$

Then $\mathcal{G} = \langle\Sigma, V, R, S\rangle$ is a _CFG_ which satisfies $L(\mathcal{G}) = L$.

### Theorem 2.3
> _CFL_ are closed under union, concatenation and Kleene star.
> + For every _CFL_ $L_1, L_2$, $L_1\cup L_2$ is also _CFL_
> + For every _CFL_ $L_1, L_2$, $L_1\cdot L_2$ is also _CFL_
> + For every _CFL_ $L$, $L^*$ is also _CFL_

- #### Proof(union)
Let $L_1, L_2$ be _CFL_,
$\mathcal{G}_1 = \langle \Sigma, V_1, R_1, S_1 \rangle$ for $L_1$ and
$\mathcal{G}_2 = \langle \Sigma, V_2, R_2, S_2 \rangle$ for $L_2$

Define
+ $V = V_1 \cup V_2 \cup \{S\}$
+ $R = \{S\rightarrow S_1|S_2\}\cup R_1\cup R_2$

Then $\mathcal{G} = \langle\Sigma, V, R, S\rangle$ is a _CFG_ for $L$ which satisfies $L = L_1\cup L_2$ is a _CFL_.

- #### Proof(concatenation)
Let $L_1, L_2$ be _CFL_,
$\mathcal{G}_1 = \langle \Sigma, V_1, R_1, S_1 \rangle$ for $L_1$ and
$\mathcal{G}_2 = \langle \Sigma, V_2, R_2, S_2 \rangle$ for $L_2$
Define
+ $V = V_1 \cup V_2 \cup \{S\}$
+ $R = \{S\rightarrow S_1S_2\}\cup R_1\cup R_2$


Then $\mathcal{G} = \langle\Sigma, V, R, S\rangle$ is a _CFG_ for $L$ which satisfies $L = L_1\cdot L_2$ is a _CFL_.

- #### Proof(Kleene star)
Let $L$ be _CFL_, $\mathcal{G} = \langle \Sigma, V, R, S \rangle$ for $L$
Define
+ $V' = V$
+ $R' = \{S'\rightarrow\epsilon|SS'\}\cup R$


Then $\mathcal{G'} = \langle\Sigma, V', R', S'\rangle$ is a _CFG_ for $L$ which satisfies $L' = L^*$ is a _CFL_.
:::info
__Relationship__
By Remark 2.4, we know that there is _CFL_ which is not Regular Language.
:::
:::warning
___CFL_ are not closed under intersection and complement__
Assume that we have already known _CFL_ are not closed under intersection(by pumping lemma), we can show _CFL_ are not closed under complement :
Consider $L_1\cap L_2$, which is not _CFL_, by De Morgan's laws, we have
$$
L_1\cap L_2 = \lnot(\lnot L_1 \cup\lnot L_2)
$$
Thus, _CFL_ are also not closed under complement.
:::

:::warning
__Question__
There are _CFL_ $L_1, L_2$ s.t.
+ $L_1\nsubseteq L_2 \mbox{ and }L_2\nsubseteq L_1$
+ $L_1, L_2$ are NOT regular

but $L_1\cap L_2$ is _CFL_(???)
:::

### Pumping Lemma for CFL
> Let $\mathcal{G}=\langle\Sigma, V, R, S\rangle$ be a _CFG_. Suppose $M = \max_{A\rightarrow w\in R}|w|$.
> For every $u\in L(\mathcal{G})$ s.t. $|u|\ge M^{|R|}+1$, $u$ can be partition into : $u = sxyzt, |x| + |z| \ge 1$, and for every $i\ge 0$,
> $$sx^iyz^it\in L(\mathcal{G})$$

示意圖：
> 上課講的是$|u|\ge M^{|V|+1}$，但是是差不多的意思，就是至少一個 symbol 被 derive 出兩次以上。

### Push-down automata(PDA)
好網站(表示方式有點不同)：https://mropengate.blogspot.com/2015/04/formal-language-ch7-pushdown-automaton.html
> PDA -- 帶有"一個" stack 的自動機

#### Parameters
__Push-down automata__ _PDA_ $\mathcal{A}=\langle\Sigma, \Gamma, Q, q_0, 𝐹, \delta\rangle$
+ $\Sigma$ is the alphabet(_input_).(和_DFA_相同)
+ $\Gamma$ is the alphabet(_stack_).
+ $Q$ is a finite set of states.(和_DFA_相同)
+ $q_0\in Q$ is the initial state.(和_DFA_相同)
+ $F\subseteq Q$ is the set of accepting states.(和_DFA_相同)
+ $\delta \subseteq Q\times(\Sigma\cup\{\epsilon\})\times\Gamma^*\times Q\times\Gamma*$ is the transition function.

> $(p, x, y, q, z)\in\delta$ 通常寫成：$(p, x, \mbox{pop}(y))\rightarrow (q, \mbox{push}(z))$，在 $p$ 這個 state 讀到 $x$ 這個 input，且 stack 中最上面是 $y$ 時，移動到 $q$ 這個 state，並且 pop($y$) 後 push($x$)。
> 這裡可以一次 push 跟 pop 一個 string，因為等價於多次 pop 和 push 單一字元的操作。
>
> 另一種常見表示法：
> 

+ A configuration of $\mathcal{A}$ : $(q, u)\in Q\times\Gamma^*$(一個 state 配上 stack 的內容)
+ For two configuration :
$$(p_0, v_0)\vdash_{b}(p_1, v_1)$$
if there is a transition $(p_0, b, \mbox{pop}(y))\rightarrow(p_1, \mbox{push}(z))\in\delta$, s.t. for some $w$
- $v_0 = wy$
- $v_1 = wz$
> 示意圖：
> 

### Equivalence between CFG and PDA
> + For every _CFG_ $\mathcal{G}$, there is a _PDA_ $\mathcal{A}$ such that $L(\mathcal{A}) = L(\mathcal{G})$, and
> + For every _PDA_ $\mathcal{A}$, there is a _CFG_ $\mathcal{G}$ such that $L(\mathcal{A}) = L(\mathcal{G})$.

+ #### Proof (statement 1)
Let _CFG_ $\mathcal{G} = \langle\Sigma, V, R, S\rangle$,
Define :
+ $\Gamma = \{\epsilon, X\}\cup V\cup \Sigma$
+ $Q = \{p, q, r\}$
+ $q_0 = p$
+ $F = \{r\}$
+ $\delta :$
- $(p, \epsilon, \mbox{pop}(\epsilon))\rightarrow(q, \mbox{push}(XS))$
- $(q, \epsilon, \mbox{pop}(X))\rightarrow(r, \mbox{push}(\epsilon))$
- $\forall A\rightarrow w\in R, (q, A, \mbox{pop}(A))\rightarrow(q, \mbox{push}(w^r))$
- $\forall a\in \Sigma, (q, a, \mbox{pop}(a))\rightarrow (q, \mbox{push}(\epsilon))$

Than $\mathcal{A}=\langle \Sigma, \Gamma, Q, q_0, F, \delta\rangle$ is a _PDA_ which satisfies $L(\mathcal{A}) = L(\mathcal{G})$.
> Example :
> 

- #### Proof (statement 2)
> potential function的概念、兩端往中間夾

Let _PDA_ $\mathcal{A} = \langle\Sigma, \Gamma, Q, q_0, F, \delta \rangle$,
Define :
+ $V = \{A_{pq}| p, q \in Q\}$
+ $S = A_{q_0, q_{accept}}$
+ $R :$
- $\forall p, q, r, s\in Q,\ \forall t\in\Gamma,\ \forall a, b\in\{\epsilon\}\cup\Sigma$ s.t. $(p, a, \mbox{pop}(\epsilon))\rightarrow(r, \mbox{push}(t))$ and $(q, b, \mbox{pop}(t))\rightarrow(s, \mbox{push}(\epsilon))$
$$A_{pq}\rightarrow aA_{rs}b$$
( t 在某個時間被 push，之後在某個時間被 pop 出來)
- $\forall p, q, r\in Q$
$$A_{pq}\rightarrow A_{pr}A_{rq}$$
- $\forall p\in Q$
$$A_{pp}\rightarrow \epsilon$$

Than $\mathcal{G}=\langle \Sigma, V, R, S\rangle$ is a _CFG_ which satisfies $L(\mathcal{A}) = L(\mathcal{G})$.

### Homework 2.4
> Prove that if $L$ is _CFL_ and $K$ is regular, then $L\cap K$ is _CFL_.

- #### Proof
Let $\mathcal{A}_1$ is _PDA_ for $L$, and $\mathcal{A}_2$ is _DFA_ for $K$, where $\mathcal{A}_1 = \langle\Sigma_1, \Gamma, Q_1, q_{01}, F_1, \delta_1\rangle$ and $\mathcal{A}_2 = \langle\Sigma_2, Q_2, q_{02}, F_2, \delta_2\rangle$.
Define :
+ $\Sigma = \Sigma_1\cap\Sigma_2$
+ $Q = Q_1\times Q_2$
+ $q_0 = (q_{01}, q_{02})$
+ $F = F_1\times F_2$
+ $\delta :$
- $\forall a\in\Sigma, \forall x, y\in\Gamma$, where $(q_{i}, a, \mbox{pop}(x))\rightarrow(q_{j}, \mbox{pop}(y))$ for $q_{i}, q_{j}\in Q_1$ and $(p_{i}, a)=p_{j}$ for $p_i, p_j\in Q_2$ :
$((q_i, p_i), a, \mbox{pop}(x))\rightarrow((q_j, p_j), \mbox{push}(y))$

- $\forall x, y\in\Gamma$, where $(q_i, \epsilon, \mbox{pop}(x))\rightarrow(q_j, \mbox{push}(y))$ for $q_i, q_j\in Q_1$ and for $p_i\in Q_2$ :
$((q_i, p_i), \epsilon, \mbox{pop}(x))\rightarrow((q_j, p_i), \mbox{push}(y))$

Then $\mathcal{A}$ is a _PDA_ which satisfies $L(\mathcal{A}) = L(\mathcal{A}_1)\cap L(\mathcal{A}_2)$, and by the equivalence between CFG and PDA, it is a _CFL_.
:::info
__Technique__
We can use Regular Closure to prove or disprove a language is context-free or not.
> Example 1 :
> Prove that $L=\{a^nb^n|n\neq 100, n\ge 0\}$ is context-free.
> + We know that $L_1=\{a^nb^n|n\ge 0\}$ is context-free.
> + We know that $L_2=\{a^{100}b^{100}\}$ is regular, thus $\overline{L_2} = \Sigma^* - \{a^{100}b^{100}\}$ is regular.
>
> Thus, $L=L_1\cap\overline{L_2}$ is context-free.
> ____
> Example 2 :
> Prove that $L=\{w:n_a=n_b=n_c\}$ is NOT context-free.
> + If $L$ is context-free, then $L\cap\{a^*b^*c^*\}=\{a^nb^nc^n\}$ is context-free __(contradiction)__
>
> Thus, $L$ is not context-free.
:::

:::info
:::

## Lesson 3(Decidable and Undecidable Languages)