keyword：有限状态机, 动态规划, 地址分析, 地图搜索
作者在本章通过地图导航技术这个应用背景介绍了有限状态机和动态规划这两个关键技术。
地图导航 = 卫星定位 -> 地址识别（有限状态机） -> 规划最优路径（动态规划）
有限状态机和地址分析
地址识别的问题：
- 上下文相关文法，例如某一条路的位置要先看它所在的省市区县（核心问题）
- 地址的模糊匹配
对于核心问题，地址的文法是上下文有关文法中相对简单的一种因此有许多识别和分析方法最有效的是有限状态机。
有限状态机是一个特殊的有向图，包括一些状态（节点）和连接这些状态的有向弧。每个有限状态机都有一个开始状态和终止状态，
以及若干中间状态。每条弧上带有从一个状态进入下一个状态的条件。
因此，可以通过一些有效的地址来建立状态机，之后在此有限状态机上通过地址字符匹配算法进行地址识别。至于如何解决地址的模糊匹配问题， 科学家们提出了基于概率的有限状态机（等效于离散的马尔可夫链统计语言模型）。
动态规划和导航
全球导航的关键算法是计算机科学图论中的动态规划（Dynamic Programing）算法。 作者这里并没有非常详细的介绍DP算法，只是介绍了大概的思想和如何应用到导航（之后计划整理一篇DP相关的blog，补在这里）。
有限状态机模型和有限状态传感器
有限状态机的数学模型：
有限状态机是一个五元组（A, S, s0, f, e），其中：
A 是输入符号的集合；
S 是一个非空的有限状态集合；
s0 是S中一个特殊状态，起始状态；
f 是一个从空间S乘A到S的映射函数，即f:SXA -> S；
e 是S中的另一个特殊状态，终止状态。
注：这里的映射函数f对于一些变量，即状态和输入符号的组合可能没有合适的对应状态（函数值），这时有限状态机就会发出出错信号。
有限状态机在语音识别和自然语言理解中起着非常重要的作用，不过这些领域使用的是一种特殊的有限状态机：加权的有限状态传感器
（Weighted Finite State Transducer, WFST）。WFST的特殊性在于它的每个状态由输入和输出符合定义，状态可以有不同的输入和输出，
如果这些输入和输出的可能性不同，即赋予了不同权重，那么相应的WFST就是加权的。
在自然语言处理中，任何一个词的前后二元组都可以对应WFST的一个状态，因此WSFT是天然的自然语言处理和分析工具和解码工具。
