Automata dot script generator

BUPT Summer Camp Topology Map Practice Project Materials Summary--Script Design of Automata Dot Drawing Based on C Language

基于c语言的自动机dot脚本生成器

用到的基础dot语法

dot图表定义:大小和布局

digraph 图名{
    size=10    //定义画布大小10英寸
    rankdir=TD       //设置元素排布为from top to down
}

用到的dot图形和线条的定义

digraph gg{
    a->b[lable="mm"] //普通单项箭头实线,标注mm
    a[shape=circle]       //圆形节点
    b[shape=doublecircle]  //同心圆节点
     //定义自动机开头的纯文本箭头
    start[shape=none,label=""]
    start->a[label="start"]
}

参数设计

经过实验，画布大小为节点数量*2比较合适

用到的自动机知识

DFA

有五种组成：
1. 状态符号集
2. 字母表(能接受语言的字符串集)
3. 开始状态
4. 终结状态或者接受状态
5. 状态转移向量
DFA中状态转移只能够由一个确定的状态遇到一个非空字母转移到一个确定的状态

NFA

有五种组成：
1. 状态符号集
2. 字母表(能接受语言的字符串集)
3. 开始状态
4. 终结状态或者接受状态
5. 状态转移向量
NFA中状态转移是不确定的，经过一个确定的字母后能够转移到多种状态

ε-NFA

有五种组成：
1. 状态符号集
2. 字母表(能接受语言的字符串集)
3. 开始状态
4. 终结状态或者接受状态
5. 状态转移向量
ε-NFA中一个状态可以接受空字母转移到若干状态

PDA

有七个部分组成
1. 状态集合
2. 字母表
3. 栈符号集
4. 开始状态
5. 终止状态或者接受状态集合
6. 初始栈符号集合
7. 状态转移向量

图灵机

七个组成:
1. 有穷状态集
2. 有穷输入符号集
3. 有穷带符号集
4. 初始状态
5. 接受状态集
6. 空格/空白符号
7. 状态转移向量

数据格式设计

有穷状态自动机的数据格式设计

A,B,C,D    //第一行是状态集合
1,2,3    //第二行是符号集合，用,隔开
A     //第三行是开始状态，只能是一个字符
C,D    //第四行是终结状态集合，能够输入多个，不过一般来说不能和开始状态重复
[ A,1,B A,3,D B,2,C B,3,D ]   
//第五行开始是状态转移输入，用[开始，空一个再开始输入状态转移，
//每个状态转移方程的输入格式如右，开始状态，遇到字符，跳转状态
//每个输入的状态之间空一格
//完成输入状态之后，需要空一格，输入]标记结束输入状态

ps:状态转移输入允许换行

//上图的转态转移允许输入格式如下
[ A,1,B A,3,D
B,2,C B,3,D ]

ps2:允许注释

//文件中允许出现注释，能够识别注释并处理
//可以在任何地方加入 //注释，注释后面的语句会被忽略

下推自动机的格式设计

A,B,C,D    //第一行是状态集合
1,2,3    //第二行是字母表
F,Z,M,N     //第三行是栈符合集
A     //第四行是开始状态，只能是一个字符
C,D    //第五行是终结状态集合
Z     //初始栈底符号
[ 
A>B:2,Z/1Z 
B>C:3,N/e 
A>D:2,1/M1 ]
//状态转移向量输入同样是以[开头，空一格开始，
//以空一格加]结束。
//每个状态转移向量以一个空格隔开

ps:状态转移向量的意义

A>B:2,Z/1Z
表示当前状态为A,当前栈顶元素为Z，遇到了字母2，则取出Z后
再依次放入Z,1。操作完成后栈顶元素为1,并且状态跳转为B

B>C:3,N/e
其中e表示空符号，这个转移向量表示空转移。
当前状态为B,栈顶为符号为N,遇到3则取出N，放入空号，也就是
消去了N,并且状态跳转到C

图灵机数据格式设计

A,B,C,D    //第一行是状态集合
1,2,3    //第二行是字母表
M,Q,Z    //第三行是带符号集合,它总是包含字母表
e    //第四行是空白带符号定义
A    //第五行是开始状态
C,D    //第六行是终止带符号
[         //状态转移向量
A>B:M/Q,L
B>C:Q/Z,R
]

关于状态转移向量的解释