2016/11/3 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

• Chap 6 Simplification of Context-Free Grammars and Normal Forms
• Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]

• Two Important Normal Forms [ pdf ] HW6.2 [ pdf ]
• A membership Algorithm for Context-Free Grammars [ pdf ] Sol_6.3 [ pdf ]

• Assignment 1 [ pdf ]
• Key to Assignment 1 [ pdf ] 

- - -

關於作業講解, 我目前還欠4-2, 4-3, 6-2, 6-3 沒有錄
以及這次的 Assignment1

- - -

今天講了6-1~7-1

6-1 講簡化一個context-free grammar的方法
6-2 介紹兩個context-free grammar的Normal Form, 分別是Chomsky和Greibach
6-3 講CYK algorithm
7-1 介紹什麼是push-down automata (npda)


- - -

前言

• given w, G, 判斷一個w是否屬於L(G), 這個過程叫做parsing
• context-free grammar <-> push-down automata

Ch 6.1
簡化一個context-free grammar的方法包含以下三步驟:

• remove empty string
• substitution method
• remove useless sentence(無限loop,走不到final的那些)

關於這個簡化過程,我有打算錄一下視頻介紹, 因為很trivail很容易忘

Ch6.2
Chomsky Normal Form: 所有grammar都符合A->BC or A->a的形式
Greibach Normal Form: 所有grammar都符合A->ax的形式 (很像s-grammar)

Ch6.3 CYK algorithm (用到演算法中的Dynamic Programming)

Ch7.1 push-down automata (npda)
這個很有趣, 我也有打算錄一下視頻, 講一下課本2個例題
不然也可以用key word "push-down automata"去google一下