当前位置: 首页 > 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; #旅游卡服务#...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...