当前位置: 首页 > news >正文

编译原理1

 NFA&DFA

在正规式的等价证明可以借助正规集,也可以通过有限自动机DFA来证明等价,以下例题是针对DFA证明正规式的等价,主要步骤是①NFA;②状态转换表; ③状态转换矩阵; ④化简DFA;

文法和语言

文法通常表示成 四元组 G[S] = ( V T V N S ξ):
(1)   V T 为终结符号集 ,这是一个非空有限集,它的每个元素 称为 终结符号
(2)   V N 为非终结符号集 ,它也是一个非空有限集,每个元 素称为 非终结符号 且有 V T ∩V N  = Φ
(3)  S 为文法开始符 ,是一个特殊的非终结符号,即 S V N
(4)   ξ /ksi/ 是产生式的非空有限集 ,其中每个产生式 ( 或称规 ) 是一序偶 β) ,通常写作
α → β α ::= β
α β 是由终结符和非终结 符组成的符号串, α (V T V N ) + 且至少有一个非终结符, β (V T V N ) *

例:产生标识符的文法

例:奇数集合,不允许出现以0开头的奇数文法 

例:上下文无关文法描述正规表达式 

基本概念: 

① 句子仅含有终结符,是特殊的句型;

②文法开始符号一定是句型

③文法产生的句子的全体为文法产生的语言;(标识符、表达式i+i*i都是语言,都由非终结符组成) 

④文法确定,则语言一定确定;反之,不一定可以由语言唯一确定文法;

⑤文法产生语言的过程中必须经过‘+’次推导(至少进行一次推导);

形式语言分类:

(1) 0型文法与语言

对应图灵机; 

文法G[S]的每一个产生式 都有   α->β  

α 作为产生式左端,至少有一个非终结符

β 作为产生式右端,不做要求(甚至可以为空); 

(2) 1型文法与语言

线性界限自动机,自然语言;

在0型文法的基础上要求文法产生式左端的长度要 小于等于 右端的长度;

 (3) 2型文法与语言

对应下推自动机,程序设计语言;

文法G[S]的每一个产生式 都有   A->α  

A∈非终结符

α∈(终结符和非终结符的闭包) 

(4) 3型文法与语言

对应有限自动机;

文法G[S]的每一个产生式 都有   A->α  或者  A->αB[右线性]  或者  A->Bα[左线性] 

A∈非终结符

α∈(终结符的闭包) 

关系和区别

① 1-3型文法属于 0 型文法;

② 2型 和 3型 文法不一定属于 1型 文法;

③ 1型文法 不允许有形如“”A->ε”, 2、3型文法允许;

④ 0、1型文法左边产生式 可以含有终结符或者两个以上终结符; 2、3型文法左端产生式要求单个非终结符(单非);

相关文章:

编译原理1

NFA&DFA 在正规式的等价证明可以借助正规集,也可以通过有限自动机DFA来证明等价,以下例题是针对DFA证明正规式的等价,主要步骤是①NFA;②状态转换表; ③状态转换矩阵; ④化简DFA; 文法和语…...

【信息系统项目管理师知识点速记】组织通用管理:流程管理

23.2 流程管理 通过流程视角能够真正看清楚组织系统的本质与内在联系,理顺流程能够理顺整个组织系统。流程是组织运行体系的框架基础,流程框架的质量影响和决定了整个组织运行体系的质量。把流程作为组织运行体系的主线,配备满足流程运作需要的资源,并构建与流程框架相匹配…...

前端 JS 经典:箭头函数的意义

箭头函数是为了消除函数的二义性。 1. 二义性 函数的二义性指函数有不同的两种用法,就造成了二义性,函数的两种用法:1. 指令序列。2. 构造器 1.1 指令序列 就是调用函数,相当于将函数内部的代码再从头执行一次。 1.2 构造器 …...

Java List操作详解及常用方法

Java List操作详解及常用方法 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 什么是Java List? Java中的List是一种动态数组,它允许存…...

《mysql篇》--查询(进阶)

目录 将查询结果作为插入数据 聚合查询 聚合函数 count sum group by子句 having 联合查询 笛卡尔积 多表查询 join..on实现多表查询 内连接 外连接 自连接 子查询 合并查询 将查询结果作为插入数据 Insert into 表2 select * from 表1//将表1的查询数据插入…...

数据库-MySQL 实战项目——书店图书进销存管理系统数据库设计与实现(附源码)

一、前言 该项目非常适合MySQL入门学习的小伙伴,博主提供了源码、数据和一些查询语句,供大家学习和参考,代码和表设计有什么不恰当还请各位大佬多多指点。 所需环境 MySQL可视化工具:navicat; 数据库:MySq…...

eNSP中WLAN的配置和使用

一、基础配置 1.拓扑图 2.VLAN和IP配置 a.R1 <Huawei>system-view [Huawei]sysname R1 GigabitEthernet 0/0/0 [R1-GigabitEthernet0/0/0]ip address 200.200.200.200 24 b.S1 <Huawei>system-view [Huawei]sysname S1 [S1]vlan 100 [S1-vlan100]vlan 1…...

<sa8650>QCX ID16_UsecaseRawLiteAuto 使用详解

<sa8650>QCX ID16_UsecaseRawLiteAuto 使用详解 一、前言二、ID16_UsecaseRawLiteAuto拓扑图三、UsecaseRawLiteAuto拓扑图 解析3.1 camxUsecaseRawLiteAuto.xml3.2 camxRawLiteAuto.xml四、测试一、前言 我们在使用QCX时,如果由于使用的摄像头自带了ISP,那么可能不需要使…...

为什么3d重制变换模型会变形?---模大狮模型网

在当今数字技术飞速发展的时代&#xff0c;3D建模和动画制作已经成为影视、游戏和虚拟现实中不可或缺的一部分。然而&#xff0c;即使在高级的3D软件中&#xff0c;重制(rigging)和变换(transformation)过程中仍然会面临一个普遍的问题——模型变形。这种变形可能导致动画效果不…...

ElasticSearch中的BM25算法实现原理及应用分析

文章目录 一、引言二、BM25算法实现原理BM25算法的实现原理1. 词频&#xff08;TF&#xff09;&#xff1a;2. 逆文档频率&#xff08;IDF&#xff09;&#xff1a;3. 长度归一化&#xff1a;4. BM25评分公式&#xff1a; BM25算法示例 三、BM25算法在ElasticSearch中的应用分析…...

web权限到系统权限 内网学习第一天 权限提升 使用手工还是cs???msf可以不??

现在开始学习内网的相关的知识了&#xff0c;我们在拿下web权限过后&#xff0c;我们要看自己拿下的是什么权限&#xff0c;可能是普通的用户权限&#xff0c;这个连添加用户都不可以&#xff0c;这个时候我们就要进行权限提升操作了。 权限提升这点与我们后门进行内网渗透是乘…...

ros1仿真导航机器人 hector_mapping gmapping

仅为学习记录和一些自己的思考&#xff0c;不具有参考意义。 1 hector_mapping 建图过程 &#xff08;1&#xff09;gazebo仿真 roslaunch why_simulation why_slam.launch <launch><!-- We resume the logic in empty_world.launch, changing only the name of t…...

嵌入式实验---实验五 串口数据接收实验

一、实验目的 1、掌握STM32F103串口数据接收程序设计流程&#xff1b; 2、熟悉STM32固件库的基本使用。 二、实验原理 1、STM32F103R6能通过查询中断方式接收数据&#xff0c;每接收到一个字节&#xff0c;立即向对方发送一个相同内容的字节&#xff0c;并把该字节的十六进…...

ubuntu 22.04下编译安装glog共享库

笔者是完美主义者&#xff0c;在编译opencv4.9时,有个有关glog的warn&#xff0c;就下载编译google的glog库并把它编译成shared libaray。重新编译opencv4.9时&#xff0c;该warn解除。现把编译安装glog过程记录&#xff0c;以备后查。 以下操作全程以root身份或sudo执行。 cd…...

Linux环境安装配置nginx服务流程

Linux环境的Centos、麒麟、统信操作系统安装配置nginx服务流程操作&#xff1a; 1、官网下载 下载地址 或者通过命令下载 wget http://nginx.org/download/nginx-1.20.2.tar.gz 2、上传到指定的服务器并解压 tar -zxvf nginx-1.20.1.tar.gzcd nginx-1.20.1 3、编译并安装到…...

设计模式-模板模式

简介 模板方法模式是一种行为设计模式&#xff0c;它在父类中定义了一个操作的算法框架&#xff0c;允许子类在不改变算法结构的情况下重定义算法的某些步骤。这种模式是基于继承的&#xff0c;通过抽象类将通用的代码抽取到超类中&#xff0c;同时通过具体类实现或者改写算法…...

物理删除和逻辑删除区别

物理删除和逻辑删除是数据库管理中针对记录删除操作的两种不同方式&#xff0c;它们的主要区别在于数据的实际处理和后续影响&#xff1a; 物理删除&#xff1a; 操作实质&#xff1a;物理删除会将数据记录从数据库表中彻底移除&#xff0c;包括记录所占的磁盘空间都会被释放。…...

C# 警告 warning MSB3884: 无法找到规则集文件“MinimumRecommendedRules.ruleset”

警告 warning MSB3884: 无法找到规则集文件“MinimumRecommendedRules.ruleset” C:\Program Files\Microsoft Visual Studio\2022\Professional\MSBuild\Current\Bin\amd64\Microsoft.CSharp.CurrentVersion.targets(129,9): warning MSB3884: 无法找到规则集文件“MinimumRe…...

Lua网站开发之文件表单上传

这个代码示例演示如何上传文件或图片&#xff0c;获取上传信息及保存文件到本地。 local fw require("fastweb") local request require("fastweb.request") local response require("fastweb.response") local cjson require("cjson&q…...

千益畅行,旅游卡,如何赚钱?

​ 赚钱这件事情&#xff0c;只有自己努力执行才会有结果。生活中没有幸运二字&#xff0c;每个光鲜亮丽的背后&#xff0c;都是不为人知的付出&#xff01; #旅游卡服务#...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...