Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >python实现DFA模拟程序(附java实现代码)

python实现DFA模拟程序(附java实现代码)

作者头像
chlinlearn
发布于 2022-05-10 00:36:26
发布于 2022-05-10 00:36:26
65580
代码可运行
举报
文章被收录于专栏:java老实人java老实人
运行总次数:0
代码可运行

DFA(确定的有穷自动机)

一个确定的有穷自动机M是一个五元组:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
M=(K,∑,f,SZ)
  1. K是一个有穷集,它的每个元素称为一个状态。
  2. ∑是一个有穷字母表,它的每一个元素称为一个输入符号,所以也陈∑为输入符号表。
  3. f是转换函数,是Kx∑->K上的映象。
  4. S∈K,是唯一的一个初态。
  5. Z∈K,是一个终态集,终态也称可接受状态或结束状态。

实例代码

  1. 实现文法
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
G[S]:   
S->aU|bV
U->bV|aQ
Q->aQ|bQ
  1. 状态图
  1. 代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 -*- coding: utf-8 -*- #
#@author: chlinlearn
#@createTime: 2019/4/13 14:12
#@fileName: DFA
class DFA():
    def __init__(self):
        #状态集
        self.listEdge = []
        #初态
        self.S = []
        #终态
        self.Z = []

    #判断是否是终态集
    def isZ(self,ch):
        for i in range(0,len(self.Z)) :
            if self.Z[0] == ch or self.Z[1] == ch:
                return True
            else:
                return False

    #输入
    def input(self):
        self.S = input("请输入开始符:")
        self.Z = input("请输入终态集(终集符组成的一个字符串):")
        self.Z = self.Z.split(",")
        print("请输入正规文法以exit结尾:")
        print("example:S,aZ")
        while(True):
            list = []
            inStr = input()
            if inStr=='exit':
                break
            inStr = inStr.split(',')
            # 读取第一个状态集
            s = inStr[0]
            for i in range(0,len(inStr[1])):
                #ch,ns
                if len(inStr[1])==2:
                    c = inStr[1][0]
                    n = inStr[1][1]
                    list = [s,c,n]
                    self.listEdge.append(list)
                elif len(inStr[1])==1:
                    c = inStr[1][0]
                    list = [s, c, self.Z[0]]
                    self.listEdge.append(list)

    #转换函数
    def isNextState(self,s,ch):
        for i in range(0,len(self.listEdge)):
            if s == self.listEdge[i][0] and ch == self.listEdge[i][1]:
                return self.listEdge[i][2]
        return

    def judgeDFA(self):
        print("请输入要判断的字符串:")
        while(True):
            #获取字母表
            str = input()
            if '#' in str :
                print("程序已退出,欢迎下次使用!")
                return
            temp = self.S[0]
            for i in range(0,len(str)):
                if str[i] is 'a':
                    temp = self.isNextState(temp,'a')
                elif str[i] is 'b':
                    temp = self.isNextState(temp, 'b')
                else:
                    break
            if self.isZ(temp):
                print("此字符串“属于”该文法!")
            else:
                print("此字符串“不属于”该文法!")
            print("再次判断请输入字符串(退出程序输入#):")

if __name__ == '__main__':
    DFA = DFA()
    DFA.input()
    DFA.judgeDFA()

总结

这是我在课程中的一个实验,代码手写并且可运行,是参照一个java版的代码实现的,加上自己的理解和思路把它以python的形式实现。学习别人好的地方,当然也不能照搬别人,不然能够为己用的东西少之又少。通过不同的编程语言把整个思路在理一遍能够加深自己的理解,并且能够得到一样的运行结果,说明自己的理解是对的。最后也附上对应的java版代码,有需求的童鞋可以参考喔! 欢迎访问我的个人网站www.chlinlearn.cn

附件

java版DFA

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class edge {
	
    char PriorityState;
    char ch; 
    char NextState;
    edge(char p,char c, char n){
        PriorityState = p;
        ch = c;
        NextState = n;
    }
    @Override
    public String toString() {
        return "edge [PriorityState=" + PriorityState + ", ch=" + ch + ", NextState=" + NextState + "]";
    }
}
/**DFA的构造*/
public class DFA {
    static List<edge> listEdge = new ArrayList<edge>();//状态集
    //static HashMap<edge, Character> mapEdge = new HashMap<>();
    static String S;//初态集
    static String Z;//终态集
    //flag is here
    static boolean judeZ(char ch){       
        for(int j=0; j<Z.length(); j++){
            if(Z.charAt(j)==ch) return true;
        }
        return false;
    }
    static void input() {
        Scanner in = new Scanner(System.in);
        String instr = null;
        String subStr[] = null;
        System.out.println("请输入开始符:");
        S = in.next();
        System.out.println("请输入终态集(终集符组成的一个字符串):");
        Z = in.next();
        System.out.println("请输入正规文法以end结尾(形式如下图):");
        System.out.println("----------");
        System.out.println("|  S-aU  |");
        System.out.println("|  S-bV  |");
        System.out.println("|  U-bV  |");
        System.out.println("|  ....  |");
        System.out.println("|  end   |");
        System.out.println("----------");
        while(in.hasNext()){
            instr = in.next();
            if("end".equals(instr)) 
            	break;
            subStr = instr.split("-|\\|");//连字符
            System.out.println("subStr:"+subStr);
            String s = subStr[0];//读取一行f(转换函数)
            System.out.println(s);
            for(int i=1; i<subStr.length; i++){
                edge e = null;
                System.out.println(subStr[1]);
                if(subStr[i].length()==2){
                    char c = subStr[i].charAt(0);//字母表
                    char n = subStr[i].charAt(1);//状态集
                    listEdge.add(new edge(s.charAt(0),c,n));//f(S,a)=U
                }
                
                if(subStr[i].length()==1){
                    char c = subStr[i].charAt(0);
                    listEdge.add(new edge(s.charAt(0),c,Z.charAt(0)));
                }
            }
        }
    }
    
    static char judeNextState(char s,char ch){
        for(int i=0; i<listEdge.size(); i++){
            if(s==listEdge.get(i).PriorityState && ch==listEdge.get(i).ch){
                return listEdge.get(i).NextState;
            }
        }
        return '0';
    }
    
    static void judeDFA(){
        Scanner in = new Scanner(System.in);
        System.out.println("请输入要判断的字符串:");
        while(in.hasNext()){
            String str = in.next();
            if(str.equals("#")){
                System.out.println("程序已退出,欢迎下次使用!");
                return;
            }
            char temp = S.charAt(0);
            int i=0;
            //System.out.println(temp+" "+mapEdge.get(e));
            for(; i<str.length(); i++){
                //System.out.println("temp="+temp);
                if(str.charAt(i)=='a'){
                    temp = judeNextState(temp, 'a');
                }
                else if(str.charAt(i)=='b'){
                    temp = judeNextState(temp, 'b');
                }
                else break;
            }
            //flag is here
            if(i>=str.length() && judeZ(temp)) System.out.println("此字符串“属于”该文法!");
            else System.out.println("此字符串“不属于”该文法!");
            System.out.println("再次判断请输入字符串(退出程序输入#):");
        }
        
    }
    
    /*main*/
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DFA.input();
        DFA.judeDFA();
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-06-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
8 条评论
热度
最新
新蓝天
新蓝天
回复回复点赞举报
天水蓝天工程机械职业技术培训学校
天水蓝天工程机械职业技术培训学校
回复回复点赞举报
自然和谐一蓝天世界职业技能教育培训
自然和谐一蓝天世界职业技能教育培训
回复回复点赞举报
蓝天世界易经科技
蓝天世界易经科技
回复回复点赞举报
代金券可以叠加使用吗
代金券可以叠加使用吗
回复回复点赞举报
非常棒的活动,加入加入!!!不多说了,我去加入~
非常棒的活动,加入加入!!!不多说了,我去加入~
回复回复点赞举报
已经加入了腾讯云的自媒体分享计划哦。嘻嘻
已经加入了腾讯云的自媒体分享计划哦。嘻嘻
回复回复点赞举报
给力,去邀请自己的自媒体朋友来搞啊!
给力,去邀请自己的自媒体朋友来搞啊!
回复回复点赞举报
推荐阅读
编辑精选文章
换一批
简单的词法设计——DFA模拟程序
通过实验教学,加深学生对所学的关于编译的理论知识的理解,增强学生对所学知识的综合应用能力,并通过实践达到对所学的知识进行验证。通过对 DFA 模拟程序实验,使学生掌握词法分析的实现技术,及具体实现方法。通过本实验加深对词法分析程序的功能及实现方法的理解 。
Angel_Kitty
2019/01/07
2K0
我整理了50道经典Java算法题,直接进了字节跳动!!
作者个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了精准定时调度方案,经受住了生产环境的考验。为使更多童鞋受益,现给出开源框架地址:
冰河
2020/10/29
1.4K0
“高级Java编程复习指南:深入理解并发编程、JVM优化与分布式系统架构“
4. 输⼊两个字符串a和b,字符串内容为⼆进制数字,求两个字符串相加的结果, 加法计算⽅法以⼆进制⽅式计算,并返回对应的字符串结果。要求程序尽可能 的⾼效。
学无止尽5
2024/11/29
1780
“高级Java编程复习指南:深入理解并发编程、JVM优化与分布式系统架构“
基于java的学生信息管理系统源代码(javaweb学生管理系统源代码)
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/128597.html原文链接:https://javaforall.cn
全栈程序员站长
2022/07/28
2.6K0
利用 DFA 算法实现文字过滤
DFA 全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA 中不会有从同一状态出发的两条边标志有相同的符号。
JMCui
2019/11/27
1.7K0
java学生成绩管理系统
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/158429.html原文链接:https://javaforall.cn
全栈程序员站长
2022/09/14
2.5K0
java学生成绩管理系统
dfa算法c语言,用c语言采用模拟dfa算法编写一个扫描器.docx
DFA定义:一个确定的有穷自动机(DFA) M是一个五元组:M= ( K,厶f, S, Z)其中
全栈程序员站长
2022/07/23
1.1K0
Java实现:String类型
题目:分析以下需求,并用代码实现:(1)从键盘循环录入录入一个字符串,输入"end"表示结束           (2)将字符串中大写字母变成小写字母,小写字母变成大写字母,其它字符用"*"代替,并统计字母的个数               举例:键盘录入:Hello12345World               输出结果:hELLO*****wORLD               总共10个字母
用户7886150
2020/12/07
6120
java编写简单的语法分析预测程序
编译原理课程中,编了一个简单的语法分析预测程序,这个程序时根据固定的文法得到预测分析表,然后编写程序来判断表达式是否会正确推到出来。
用户7886150
2020/12/13
6600
经典KMP算法C++与Java实现代码
  KMP算法是一种字符串匹配算法,由Knuth,Morris和Pratt同时发现(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。比较流行的做法是实现一个next()函数,函数本身包含了模式串的局部匹配信息。由于next函数理解起来不太容易,本文同样是基于空间换时间的做法,但将采用另一种代码实现,希望可以更方便读者理解!
云海谷天
2022/08/09
4100
经典KMP算法C++与Java实现代码
【15】JAVASE-常用工具类【从零开始学JAVA】
Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机,Java 仍是企业和开发人员的首选开发平台。
用户4919348
2024/05/25
1740
【15】JAVASE-常用工具类【从零开始学JAVA】
【编程题】Java编程题四(10道)
【编程题】Java编程题四(10道) 【程序31】 题目:将一个数组逆序输出。 import java.util.*; public class lianxi31 { public static void main(String[] args) { Scanner s = new Scanner(System.in); int a[] = new int[20]; System.out.println("请输入多个正整数(输入-1表示结束):"); int i=0,j; do{
Java帮帮
2018/03/19
1.6K0
编译原理自动生成LR(0)分析表Python实现
对于LR文法,我们可以自动构造相应的LR分析表。为了构造LR分析表,我们需要定义一个重要概念——文法的规范句型“活前缀”。
里克贝斯
2021/05/21
1.9K0
编译原理自动生成LR(0)分析表Python实现
波形图(人人网2017春招真题)
小明正在做物理实验,他在示波器上观察波形。在每一时刻,他能观察到两种可能的波形,一种是水平波形,由两个下划线组成:”__”。一种是脉冲波形,由一个斜杠和一个反斜杠组成:”/\”。 小明观察到一个水平波形就在数据表上记录一个减号”-”,观察到一个脉冲波形就在数据表上记录一个加号”+”。如小明观察到波形”_/_/\/__”,他就会记录”-+-++-”。 现在小明想实现纪录序列与波形之间的转化,你能帮助他吗?
AI那点小事
2020/04/20
4790
编译原理:第三章 词法分析
从左至右逐个字符地对源程序进行扫描,产生 一个个的单词符号,把作为字符串的源程序改造成为单词符号串的中间程序或者说:逐个读入源程序字符,并按照词法规则分割成一系列单词,再转换成单词串,同时进行词法检查。
Here_SDUT
2022/08/09
4.7K0
编译原理:第三章 词法分析
java之Scanner详解「建议收藏」
Scanner reader=new Scanner(System.in);
全栈程序员站长
2022/09/09
6290
【Java】用java实现统计字符串个数
统计某种字符串中某个字符或某个字符串出现的次数,以及每次出现的索引位置 有如下字符串: 患者:“大夫,我咳嗽得很重。” 大夫:“你多大年记?” 患者:“七十五岁。” 大夫:“二十岁咳嗽吗”患者:“不咳嗽。” 大夫:“四十岁时咳嗽吗?” 患者:“也不咳嗽。” 大夫:“那现在不咳嗽,还要等到什么时咳嗽?” 需求:请统计出该字符中*“咳嗽*”二字的出现次数。 代码如下:
用户7886150
2021/04/06
1.7K0
JAVA零基础小白学习教程之day10-API&Object&String
API(Application Programming Interface),应用程序编程接口。Java API是一本程序员的字典 ,是JDK中提供给 我们使用的类的说明文档。这些类将底层的代码实现封装了起来,我们不需要关心这些类是如何实现的,只需要学习这些类如何使用即可。所以我们可以通过查询API的方式,来学习Java提供的类,并得知如何使用它们。
张哥编程
2024/12/13
840
【背诵①】保姆级 | 零基础备赛蓝桥杯Java组| 字符串
4、使用 compareTo(String anotherString) 方法比较字符串的字典顺序:
命运之光
2024/04/15
1060
编程入门、进阶100例(16-20)
题外话:学编程越是学到后面,我就越发的感受到,刷题是提升编程技能最快的方式。学编程从入门到进阶,再到高阶,现在从16题开始就会有一些难度了,这里我会整理一些我刷过的一些题目。
Gorit
2021/12/09
5110
编程入门、进阶100例(16-20)
推荐阅读
相关推荐
简单的词法设计——DFA模拟程序
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验