2016年10月

子集构造法实现NFA转DFA

    import os
    import pprint
    import argparse
    
    dic = {}
    az = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    count = 0
    DFAlist=[]
    
    #记录路径信息到DFA列表
    def recordDFA(list_1, cha, list_2):
        global DFAlist
        lis=[list_1,cha,list_2]
        DFAlist.append(lis)
    #输出DFA列表
    def outputDFA():
        global DFAlist
        global dic
        print('                     NFA状态               DFA状态   读取字符   到达DFA状态             到达NFA状态')
        for eachlist in DFAlist:
            key1=''
            key2=''
            for each in eachlist:
                for key in dic.keys():
                    if dic[key]==each and key1=='':
                        key1=key
                    elif dic[key]==each and key1!='':
                        key2=key
            print(str('%40s'%eachlist[0])+'     '+key1+'       '+str(eachlist[1])+'       '+key2+'      '+str(eachlist[2]))
    
    #类中含list与标记flag
    class listflag:
        unsignedcount = 0
    
        def __init__(self, list_0):
            self.list = list_0
            self.flag = 1
            listflag.unsignedcount += 1
    
        def getlist(self):
            return self.list
    
        def getflag(self):
            return self.flag
        #将对象设置标记
        def setflag(self, flag):
            if flag == 1:
                listflag.unsignedcount += 1
            else:
                listflag.unsignedcount -= 1
            self.flag = flag
        #返回当前是否含有未被标记的对象
        @staticmethod
        def isHaveUnsignedFlag():
            return listflag.unsignedcount > 0
    
    
    # 打开NFA文件并将内容转换为三维列表并返回
    def openNFA(path):
        list_3 = []
        if os.path.exists(path) != True:
            print('The path is wrong')
        try:
            with open(path, 'r') as file:
                for line in file.readlines():
                    line = line.rstrip('\n')  # 去掉每一行的换行符
                    tmp_list = line.split(';')  # 存在通过一条边有多个终点的节点,见目的节点放在列表中
                    for i in range(0, len(tmp_list)):
                        tmp_list[i] = tmp_list[i].split(',')
                    list_3.append(tmp_list)  # 生成三维列表
        finally:
            file.close()
        return list_3
    
    
    # 参数:起始状态(list) NFA列表 经过的边(z表示其他) 返回目标状态列表
    def moveTo(state_start_list, list_3, border='z'):
        row = len(list_3)  # 三维列表行 列 起始状态位置 边位置 返回列表
        col = len(list_3[0])
        state_row = 0
        border_col = 0
        list_end = []
        for i in range(0, col):  # 取得边的位置
            if list_3[0][i][0] == border:
                border_col = i
                break
        for state_start in state_start_list:
            state = str(state_start)
    
            for i in range(0, row):  # 取出起始状态位置
                if list_3[i][0][0] == state:
                    state_row = i
                    break
            if list_3[state_row][border_col][0] == 'void':  # 获得对应NFA表信息并处理
                pass
            else:
                for each in list_3[state_row][border_col]:  # 将能到达的状态放入返回列表中
                    list_end.append(each)
        return sorted(list_end)
    
    
    # 求一个起始状态集合的闭包
    def closureT(T_list, list_3):
        list = T_list
        states = []
        for item in T_list:
            states.append(str(item))  # 详见算法
        while len(list) != 0:
            state = list.pop()
            u = moveTo([state], list_3)
            for each in u:
                if states.count(each) == 0:
                    states.append(each)
                    list.append(each)
        return sorted(states)
    
    
    # 给出初始状态s0与NFA三维列表 输出DFA
    def DFA(state0, list_3):
        global dic
        global count
        global az
        Dstates = []
        #计算初始状态闭包
        closure0 = closureT(state0, list_3)
        #将旧状态与新状态映射放在字典中
        dic[az[count]]=closure0
        count+=1
        #详见算法
        temp = listflag(closure0)
        Dstates.append(temp)
        characters = []
    
    
        for character in list_3[0][1:len(list_3[0]) - 1]:
            characters.append(character[0])
        while listflag.isHaveUnsignedFlag():
            T = []
            for each in Dstates:
                if each.getflag() == 1:
                    T = each.getlist()
                    each.setflag(0)
                    break
            for character in characters:
                U = closureT(moveTo(T, list_3, border=character), list_3)
                flag = True
                for obj in Dstates:
                    if U == obj.getlist():
                        flag = False
                if flag:
                    Dstates.append(listflag(U))
                    dic[az[count]]=U
                    count+=1
    
                #print('%40s'%str(T)+'--->'+character+'--->'+str(U))
                #记录路由信息
                recordDFA(T,character,U)
        return Dstates
    
    def parse_args():
        parser = argparse.ArgumentParser()
        help="Example NFA.txt:(line0)\n"+ \
             "10;0;1;z(line1)\n" +\
             "A;A,B;A;void(line2)\n"+ \
             "B;C;void;void(line3)\n" +\
             "C;void;void;void(line4)\n"
        parser.add_argument('-f', help=help, default='')
        args = parser.parse_args();
        return args
    if __name__=='__main__':
        args=parse_args()
        filepath=args.f
        if os.path.exists(filepath):
            temp = openNFA(filepath)
            #输出有文件得到的NFA表
            print('NFA TABLE:')
            pprint.pprint(temp)
            #获得起始状态并开始
            startcha = temp[1][0][0]
            Dstates = DFA([startcha], temp)  # 若将temp[0]作参数,由于传入的是引用,则会在后面出栈时破坏NFA表
            outputDFA()
        else:
            print('file  not  exists!')

NFA.txt

ubuntu 命令 自用

ps -ef ->显示当前所有进程
pstree ->以树状形式显示进程

tar -czf target.tar target
tar -cf result.tar f1 f2
kill -9 pid ->结束进程
kill -stop pid ->暂停进程

jobs ->查看后台进程
fg id ->将进程放到前台
bg id ->将进程放到后台

screen -S name ->新建一个名为name的screen
screen -d name/pid ->与窗口断开连接
screen -r name/pid ->重连窗口
screen -S -X id quit -> 关闭窗口
exit ->结束窗口

df -h ->查看硬盘使用空间
du -hs name->查看目录所占空间
du -s name ->查看文件夹大小
rm -rf name ->删除文件夹

free ->查看内存使用情况

sftp -oPort=2730 root@104.225.153.5 -> SFTP连接服务器
put [-r] [localfile] [serverfile] -> 上传文件
get [-r] [serverfile] [localfile] -> 下载文件
!ls -> 列出本地文件

进程间通信

        //实现进程间相互通信  system V 消息队列实现
        #include <stdio.h>
        #include <stdlib.h>
        #include <unistd.h>
        #include <sys/types.h>
        #include <sys/ipc.h>
        #include <sys/msg.h>
        #include <string.h>
        #define MAX_TEXT 20
        struct msgbuf {
            long mtype; 
            char mtext[MAX_TEXT ]; 
        };  //传输数据的结构体
        int main(int argc,char *argv[])
        {
            pid_t pid;
        
            size_t len;
            int type;
            struct msgbuf snd;
            struct msgbuf rcv;
            char buf[MAX_TEXT];
            key_t key;
            int mid,ret;
    
            key = ftok(".", 'a');
        
            if((mid = msgget(key, IPC_CREAT|0770)) == -1) {
                perror("message queue create error");
                exit(1);
            }
            printf("%d\n", mid);
            system("ipcs -q");
            printf("-----------end with type 4 and data exit--MAX_TEXT 10----------\n");
            while(1) {
               
                fputs("输入你要传送的数据类型:", stdout);
                setbuf(stdin, NULL);
                scanf("%d", &type);
                snd.mtype = type;
                fputs("输入要传送的字符数据:", stdout);
                //清空键盘缓冲区,在linux下getchar(),fflush(stdin),rewind(stdin)都不起作用
                setbuf(stdin, NULL);
                fgets(buf, MAX_TEXT, stdin);
                memcpy(snd.mtext, buf, MAX_TEXT);
                ret = msgsnd(mid, (void *)&snd, MAX_TEXT, 0);
                if(ret == -1) {
                    exit(3);
                    perror("msgsnd error");
                }
                if(strncmp(snd.mtext, "exit", 4) == 0) {
                    break;
                }
            }
            system("ipcs -q");
            pid=fork();
            if(pid==0){
                while(1) {
                ret = msgrcv(mid, (void *)&rcv, MAX_TEXT, 0, 0);
                if(strncmp(rcv.mtext, "exit", 4) == 0) {
                    printf("type: %ld    data: %s", rcv.mtype, rcv.mtext);
                    break;
                }
                if(ret == -1) {
                    exit(3);
                    perror("msgrcv error");
                }
                printf("type: %ld    data: %s", rcv.mtype, rcv.mtext);
                }
            }
            else{
                wait(NULL);
                system("ipcs -q");
                msgctl(mid, IPC_RMID, (struct msqid_ds *)0);
                system("ipcs -q");
                exit(0);
            }
        
        }