Chapter 3

FSA(automaton)--有限状态机,或者是FSM(machine)

正则表达式不仅仅用在文本的查找中, 也是一种用于描述有限状态机的方法.

用有向图来表示FSA,有nodes节点代表状态，以及连接node的与有向线段．double　circle是结束节点

使用有限状态机去识别羊说话

FSA可以用于实现正则表达式，任何一个正则表达式也可以被实现为一个FSA．输入string，返回accept　or reject

FSA又可以进一步分为DFSA和Non-Deterministic FSA即(NFSA),指的是状态机中含有一些不能确定的点，即不能根据输入的string判断当前在哪个状态．　DFSA可以转化为NFSA．

羊说话的格式是:
baaa!
baaaa!
baaaaa!
baaaaaa!

Formal language

理解就是一组"规定字符串"的集合, 而组成这个字符串的字符集是我们自己定义的字母表.比如羊语言的只含有{a, b, !},另外我们需要定义一个模型, 这个模型是我们定义的一个特殊状态机, 让字母表中的字符任意排列组合成一个字符串并与这个模型(状态机)进行匹配, 当状态机返回的结果是accept时, 也就是说这个字符串是符合我们想要的. 那么就加入到Formal language集合中去.我们可以看到, Formal language中的内容是和模型密切相关的.

除此, Formal language 很有可能是无限个字符串的集合.

第三章

stemming & lemmatization

stemming:词干解析/词干提取　抽取词的一般形式，大部分是采用缩减的方法，如cats > cat

lemmatization:词性还原 抽取词的词干或词根形式.如 drove > drive 比词干提取要复杂

morpheme词素,比单词word的颗粒度更小，定义为承担最小语义的语言单位,一个单词可以理解为含有多个词干和后缀组成．后缀又分为前缀 后缀 中缀，前后词缀.

通过词素构成单词主要有四种方式：

Inflection Derivation Compounding Cliticization

Inflection : 含有inflectional的词素，比如-s，就可以将单词和-s结合起来将名词的单数形式变为复数形式．变化后还是原来的class,这里的class应该就是词性的分类，如名词　，动词　形容词．

• word classes 介绍

Derivation:和Inflection的构成公式差不多，但通常变化后会改变原来的单词词性，　如
verb动词computerize和后缀-ation变为computerization名词．

Compounding:　简单点，　将多个单词合并为一个．如doghouse就是dog和house的合并．

Cliticization:　将一个word和一个clitic组合．clitic翻译完附着词素，很像单词的词缀，但词缀只是针对一个单词，而clitic可以附着到任何整句话和一个句子中．
如果我们使用一个不确定性FSA来识别字符串，可能在某一个有多种选择(arcs)的点上面，我们可能选择了一个错误的arc,这就导致本来应该是一个accept的字符串，我们给出了reject的结果．有三种解决办法，Back-up, Look-ahead, Parallelism(不进行选择，每一种选择都试验一遍)

• clitic 介绍

Morphological parsing

Parsing　means 输入一个单词，输出这个单词的一些语言结构．

FSA Morphological parsing

使用有限状态机这一方法来实现形态解析．

• 1.就是通过FSA构建用于解析的词典(Lexicon),构建成果之后，就可以用于单词识别．
• 2.finite-state transducer FST 理解为是一种特殊FSA，　FST 介绍
  FST　图片
• 3.FST每一步都有相应的输入和输出．