Pumping Lemma | 各种泵引理

Created2024-12-22|Updated2025-04-10|fla

|Post Views:

正则语言的泵引理

对于一个正则语言存在一个整数使得对于中的每一个长度大于等于的字符串都可以写作满足以下性质：

上下文无关语言的泵引理

对于每一个上下文无关语言都存在一个整数使得满足：

Author: Eric Li

Link: https://www.ericli.vip/2024/12/22/Fla/Pumping%20Lemma/

Copyright Notice: All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.

Related Articles

FLA Lab Report | 自动机大作业实验报告

设计思路整体上我的程序分为如下几个步骤：读取命令行参数如果有 -h 就输出帮助信息并退出如果带有 -v 或者 --verbose 参数就把fla结构体中对应的值设为true 根据命令行输入的文件后缀，判定运行的模拟类型，并记录到fla结构体中读取文件的内容，加载到对应的结构体中根据上一步判定的模拟器类型，把fla结构体传给对应的模拟器 PDA模拟器对于pda模拟器，我的设计如下：我用的面向对象的方法，每一个状态都被封装成了一个类，模拟器保存了一个迭代器指向当前的状态。每个状态提供一个 pair<bool,pair<int,string>>get_transition(char input, char stack_top) 方法，传入当前的字符、栈顶符号，返回 (是否成功，下一个状态的编号，栈顶压入符号) 具体的运行方式如下：使用 compile() 函数可以编译一个pda模拟器，经历如下步骤：传给Lexer，按照行给整个传入的文件进行划分，并丢弃所有分号后面的内容。 Lexer将每一行传给 get_statement()...

P and NP,Decidable and RE

递归语言和递归可枚举语言递归语言（decidable）要求存在一个满足如下要求的图灵机： Halt on accept Halt on reject但是递归可枚举语言（RE:Recursive enumerable）要求存在的图灵机只需要满足： Halt on accept换言之，对于 True RE可能存在某个句子，你不知道这个句子在图灵机上会不会停机正规定义：递归可枚举语言是指由图灵机定义的语言（不管是通过终止状态接受还是通过停机接受）递归语言：定义算法是一个图灵机，该图灵机通过终止状态接受，并且无论接受与否，它都注定会停机定义递归语言是由定义的，且是一个算法可判定性对于图灵可判定和图灵可识别，这两个概念如下：如果一个语言是递归语言那么这个语言是图灵可判定语言如果一个语言是递归可枚举语言那么这个语言是图灵可识别语言非递归可枚举语言这种类型的语言是存在的，因为RE的集合是可数集合，但是所有语言的集合的势势不可数的 P 和 NPP...