---
# System prepended metadata

title: 自動機 ch.5
tags: [AutomataTheoryandFormalLanguages, 110-1, NTNU, CSIE, 選修]

---

---
title: 自動機 ch.5
---
# Automata Theory and Formal Languages
NTNU 自動機理論與正規語言
##### [Back to Note Overview](https://hackmd.io/@NTNUCSIE112/NTNUNote)
##### [Back to Automata Theory and Formal Languages](https://hackmd.io/@NTNUCSIE112/AT110-1)
{%hackmd @sophie8909/pink_theme %}
###### tags: `AutomataTheoryandFormalLanguages` `110-1` `選修` `CSIE` `NTNU`
<!-- https://hackmd.io/@NTNUCSIE112/AT110-1_X -->
## Ch.05 Context-Free Languages
Parsing
- Parsing 是描述句子結構的一種方式
- 每當我們需要理解句子的含意時很重要
- 在電腦科學中，他與直譯器、編譯器等翻譯程序相關
### 5.1 Context-Free Grammars
#### Context-free grammar
- 正規文法中的產生式受到兩種方式的限制
    - LHS 必須為單一的變數
    - RHS 有一個特殊的格式
LHS/RHS 產生式的左/右邊
- 為創造更強大的文法，我們必須放寬一些限制
- 保留左側的限制，允許右側的所有東西，得到上下文無關文法
#### Definition 5.1
- 若文法 $G=(V, T, S, P)$ 中的 $P$ 都是
$A\rightarrow x$ ,  $A\in V$ and $x\in(V\cup T)^*$
- 語言 $L$ 被稱為上下文無關 i.f.f. 有一個上下文無關文法使得 $L=L(G)$
- 所有正規語言都是上下文無關的，所以一個正規語言也是上下文無關的

備註：linear grammer RHS中只有一個變數

#### Leftmost and Rightmost derivation
#### Definition 5.2
一個 derivation 中每個 step 都是由最左／右邊的變數做替換的
稱該 derivation leftmost/rightmost

#### Derivation Tree
右邊的東西為左邊東西的child
![](https://i.imgur.com/Xy3dHOI.png)
#### Definition 5.3
設 $G=(V, T, S, P)$ 為一個 cfg，一個 ordered tree 為一個 derivation tree i.f.f.
1. root 為 $S$
2. 每個 leaf 都是從 $T\cup\{\lambda\}$ 來的
3. 每個 interior vertex（不是 leaf 的 vertex），都是 $V$ 中的 label
4. 如果一個 vertex 有一個 label $A\in V$，且其 children 從左到右為 $a_1, a_2,..., a_n$ ，則 $P$ 必包含一個 production $A\rightarrow a_1a_2...a_n$
5. label 為 $\lambda$ 的 leaf 不會有 sibiling
#### Patrial derivation tree
1. 每個 leaf 都是從 $T\cup U\cup\{\lambda\}$ 來的
2. 每個 interior vertex（不是 leaf 的 vertex），都是 $V$ 中的 label
3. 如果一個 vertex 有一個 label $A\in V$，且其 children 從左到右為 $a_1, a_2,..., a_n$ ，則 $P$ 必包含一個 production $A\rightarrow a_1a_2...a_n$
4. label 為 $\lambda$ 的 leaf 不會有 sibiling

從左到右看 tree 的 leaf，忽略 $\lambda$ 的符號串稱為 tree 的 yield

#### Theorem 5.1
- 設 $G=(V, T, S, P)$ 為一個 cfg，
則 $\forall w\in L(G)$，存在一個 $G$ 的 derivation tree 其 yield 為 $w$
- 任何 derivation tree 中的 yield 都在 $L(G)$ 中
- 如果 $t_G$ 為 $G$ 中的任一個 partial derivation tree 且其 root 為 $S$，則 $t_G$ 的 yield 為 $G$ 的 sentential form
### 5.2 Parsing and Ambiguity
#### Parsing
- 找出一個 production 的序列，透過他可以導出 $w\in L(G)$
- 窮舉搜尋 parsing（一種 top-down parsing）
    - 給一個字串 $w$，我們系統性的建構所有的可能（e.g. leftmost）derivation 去看他們是否 match $w$
    - 缺點：
        - 單調、低效率
        - 


### 5.3 Context-Free Grammars and Programming Languages