编译原理中的fa是什么

‘壹’ 编译原理中的dfa是什么意思，是什么术语的缩写

DFA(确定性有限自动机)

其实就是有限自动机，deterministic finite automaton

其实我记得好像是词义分析阶段用到的一个技术。。。

‘贰’ 编译原理，如何判断一个FA是DFA还是NFA

DFA或NFA是对计算机程序的行为的抽象模型.你编写的程序其实就对应了一个自动机.简单举例来说,如果a,b可以取值0或1; 程序：if(a==1) b=1; 这个程序对应了一个自动机.
对应的自动机就有状态 (0,0),(0,1),(1,1),(1,0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时,运行程序的下一个状态就是(1,1).
画图出来就是 这4个状态作为顶点,并且有下面几条边
(0,0) --> (0,0)（自环）,(1,0)-->(1,1),(1,1)-->(1,1)（自环）,(0,1)-->(0,1)自环
存在的意义就是一种理论模型,也可以认为是一种编程思想.词法分析系也离不开 if else,这一系列的if else和条件也就组成自动机.
最经典体现自动机思想的算法就是KMP算法,你肯定学过,字符串子串匹配的算法.回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机!算法第二步将原串作为自动机输入,自动机的输出就是匹配到的子串位置或者无匹配.

‘叁’ 【编译原理】第三章：词法分析

语言
正则表达：

正则表达式可以由较小的正则表达式递归构建。每个正则表达式r定一个语言记作L(r)。

正则表达式优先级为：克林闭包>连接>或。

简单来说就是重定义。
例如：
letter -> 字母
number -> 数
d -> 整数

系统根据 当前状态 与 当前的输入信息 决定 后继行为 。
每当处理完当前输入后，状态也发生改变。

如果给定输入串x，如果存在对于该串 从初始状态到某个终止状态 的转换序列，则该串被该FA 接收 。

例：对于FA

abbaabb 是被接收的，而 abbaaba 则不被接收。

重点： 转换表 ；
一个有穷自动机可以由转换表表示。

例：

以上两种自动机都可以用正则表达式 来表示。
事实上， 正则表达式与有穷自动机是等价的 。

从人的角度看，NFA比DFA更加直观；但对于程序来说，DFA比NFA容易实现。

直接从RE转换到DFA是比较困难的，所以一般通过NFA作为中介。

DFA中的每个状态都是NFA中状态集合的一个子集。

即，先写出NFA的转换表，再通过新的状态构建出DFA。

例：

记数字为 ，字母为 ，那么标识符的正则表达式为：

这个正则表达式转换为NFA，表示如下：

这个NFA同时也是一个DFA，所以不用再进行转换。

记：
数字
数字串
小数部分
指数部分
数

即一个数由一个数字串+可选的小数部分+可选的指数部分构成。
转换为NFA，表示如下：

通过子集构造法，将NFA转换为DFA：

可以表示10进制、8进制、16进制的DFA：

‘肆’ 编译原理，如何判断一个FA是DFA还是NFA

第一个是NFA 第二个是DFA
主要区别
1）DFA没有输入空串之上的转换动作；
2）对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集；