INT201 W8

这周换一个方法记录blog，以记录自己想记录的东西为主。

---

在language的大集合里，有一部分语言被作为regular languages，测试他们是否是regular languages的方法是使用DFA & NFA & RL，pumpling lemma得出了有一部分语言是unregular的，unregular的语言不可以用DFA NFA Regular expression去define。这是就需要Grammar（content free grammar） which可以define regular languages and unregular languages

Content-free Grammar

G = (V, A, S, P)
V is a set of variables.
A is constant, terminates 阿尔法贝塔
S is a variable, state symoble
P is a set of rules (production) eg: x -> a a属于(VUA)^* 类似转移方程？
都是有限集
S –> aSb content-free意味着ab对S没有影响
L(G) = {w|wEA*, s->w}