NFA
2024-08-28 03:15:19
任意正则表达式都存在一个与之对应的NFA，反之亦然.
正则表达式 ((A*B|AC)D)对应的NFA(有向图), 其中红线对应的为该状态的ε转换, 黑线表示匹配转换
我们定义的NFA具有以下特点:
- 正则表达式中的每个字符在NFA中都有且只有一个对应状态，NFA的其实状态为0,并包含一个虚拟的接收状态
- 正则表达式中的字母所对应的状态都有一条从它指出的黑色的边，并且一个状态只能有一条指出的黑色边
- 正则表达式中的元字符所对应的状态至少含有一条指出的红色的边
ε转换
不需要扫描匹配文本中的任意字符，自动机就可以从一个状态转换到另一状态
使用 NFA模拟匹配过程:
- 首先获取初始状态通过ε转换可以到达的所有状态集合，上图为0,1,2,3,4,6
- 顺序扫描匹配文本中的字符，如果状态集合中找到匹配该字符的状态(可以使多个)，自动机就可以扫过该字符并由黑色的边转到下一个状态，这种转换成为匹配转换，由下一状态及下一状态的的ε转换生成新的状态集合，继续扫描下一个字符
- 扫描完所有字符后，如果最终到达的所有状态中包含接受状态，则匹配该字符串
源代码namespace NFA
{
public class IntList : List<int>
{
} public class Digraph
{
public int E { get; set; }
public int V { get; set; }
public IntList[] Adjs { get; set; } public Digraph(int v)
{
this.V = v;
this.E = 0;
Adjs = new IntList[v];
for (int i = 0; i < v; i++)
{
Adjs[i] = new IntList();
}
} public void AddEdge(int from, int to)
{
Adjs[from].Add(to);
E++;
} public IntList Adj(int index)
{
return Adjs[index];
}
} public class DirectedDFS
{
public bool[] Marked;
public DirectedDFS(Digraph g, int s)
{
Marked = new bool[g.V];
Dfs(g, 0);
} public DirectedDFS(Digraph g, List<int> source)
{
Marked = new bool[g.V];
source.ForEach(x =>
{
if (!Marked[x])
{
Dfs(g, x);
}
});
} public void Dfs(Digraph g, int v)
{
Marked[v] = true;
g.Adjs[v].ForEach(x =>
{
if (!Marked[x])
{
Dfs(g, x);
}
});
}
}
} namespace NFA
{
public class NFA
{
private string regex;
//NFA的ε转换有向图
private Digraph G; public NFA(string reg)
{
this.regex = reg;
Stack<int> ops = new Stack<int>();
int M = regex.Length;
G = new Digraph(M+1);
//循环状态
for (int i = 0; i < M; i++)
{
int lp = i;
if (regex[i] == '(' || regex[i] == '|')
{
ops.Push(i);
}
else if (regex[i] == ')')
{
int or = ops.Pop();
if (regex[or] == '|')
{
lp = ops.Pop();
G.AddEdge(lp, or + 1);
G.AddEdge(or, i);
}
else
{
lp = or;
}
}
if(i<M-1 && regex[i+1] == '*')
{
G.AddEdge(lp,i+1);
G.AddEdge(i + 1, lp);
}
if (regex[i] == '(' || regex[i] == '*' || regex[i] == ')')
{
G.AddEdge(i, i + 1);
}
}
} public bool Recognize(string txt)
{
List<int> pc = new List<int>();
DirectedDFS dfs = new DirectedDFS(G, 0); for (int i = 0; i < G.V; i++)
{
if (dfs.Marked[i])
{
pc.Add(i);
}
} for (int i = 0; i < txt.Length; i++)
{
List<int> match = new List<int>();
foreach (int v in pc)
{
if (v < regex.Length)
{
if (regex[v] == txt[i] || regex[v] == '.')
{
match.Add(v + 1);
}
}
}
pc = new List<int>();
dfs = new DirectedDFS(G, match); for (int v = 0; v < G.V; v++)
{
if (dfs.Marked[v])
{
pc.Add(v);
}
}
}
foreach (int v in pc)
{
if (v == regex.Length)
{
return true;
}
}
return false;
}
}
}
最新文章
- xml
- ios 提取html 字符串中的img 的地址（图片地址）
- php判断请求类型 ajax、get还是post类型
- 链队列的C/C++实现
- C++经典编程题＃5：寻找下标
- VS2008调试快捷键
- Winform 数据验证
- Oracle Pivot学习心得
- MVC4.0 上传Excel并存入数据库
- Git GUI简易使用教程
- C语言入门（18）——数组与字符串
- 饭卡------HDOJ杭电2546（还是01背包！！！！！！）
- Unity与Android交互-Unity接入高德地图实现定位以及搜索周边的功能（使用Android Studio）详细操作
- String,StringBuffer与StringBuilder
- mongoDB学习手记1--Windows系统下的安装与启动
- 手撕vue-cli配置文件——config篇
- PHP调用微博接口实现微博登录的方法示例
- 【洛谷P2822 组合数问题】
- Codeforces 1118F1 Tree Cutting (Easy Version) (简单树形DP)
- 动手创建 SSD 目标检测框架