⑴ 正则语言，上下文无关语言，非上下文无关语言这三种怎么判断出来的
能使用
正则语言
写出来或者DFA判别的就是正则语言
能使用上下文无关语言或者PDA判别的就是上下文无关语言
剩下的都是其他语言
正则语言和上下文无关语言可以使用
泵引理
判假，即所有正则语言，上下文无关均符合他们的泵引理，但是不是所有符合泵引理的都是CFG或者CFL
泵引理自行网络
⑵ 泵引理的引理应用
例1：字符串集合={ | m,n∈N ∧ n>m }不是正则的。
证明：显然∈，所以由泵引理知当p足够大时字符串中存在子串可重复。若该子串中只有0，那么当k>1时将使得0多于1，这将导致矛盾。若同时存在0,1，那么这将使0,1交替出现，同样导致矛盾。若只出现1，由泵引理知k可为0，而此时将有1不多于0，这也是矛盾的。因此该语言不是正则的。
例2：若为所有素数的二进制表示的0,1串，那么不是正则的。
证明：由初等数论易知存在任意大的素数，所以存在素数使得其二进制串长度大于泵引理阈值。将表示为，由泵引理知的二进制位串也属于，因此也是素数。由费马小定理知，所以即，又（即其可逆）所以。因此，所以| 这与为素数矛盾，故不是正则的。
⑶ 泵引理的引理描述
若 L 是正规语言，则存在一常数 n > 0 使得语言 L 中每个字串 w 的 |w| ≥ n，而当 w = xyz 时：
1.|xy| ≤ n ，
2.|y| ≥ 1 ，且
3.对所有的 k ≥ 0 ，字串 属于 L 。
证：若L为正则语言，那么存在一个DFA识别它。设其状态数为n，那么对于任意字符串w∈它被DFA识别时的状态转换为：（qn为接受状态）。因为w≥ n，所以由鸽笼原理存在状态重复，记状态所识别的字符串为y，那么易知（即是将重复状态重复k次）仍可被此DFA识别，故∈。
⑷ 如何证明一个语言是正则语言
你是在学自动机这些东西吗
只要有一个DFA或者NFA能够表述这个预言 那么他就是正则语言
DFA: 确定的有穷自动机
NFA： 不确定的有穷自动机
⑸ 怎样运用泵引理证明能被4整除的整数是正则语言
一 封闭性
正则语言之并是正则的
正则语言之交是正则的
用自动机的乘积自动机。
如果证明了3，也可以用集合运算。
正则语言的补语言是正则的
用一个 DFA 表示原来的语言，然后把非接受状态改为接受状态，把接受状态改为非接受状态。
正则语言的差是正则的
集合运算。
正则语言的反转是正则的
用一个 DFA A 表示原来的语言，把 A 改造成 RA, 先把所有箭头反转；把接受状态改为普状态；把初始状态改为接受状态。加入一个新状态作为初始状态，并发出 e 箭头指向原来的全体接受状态。
另一种方法是归纳。设语言为 L(A)，则 R(L(A)) = L(R(A))
正则语言的 kleene 闭包是正则的
正则语言的连接是正则的
二 应用举例
设字符集合为 {0,1}. 语言 L 表示由不同个数的 0,1 组成的串, 试证明其为非正则的.
用泵引理证明 L 的补语言 L'={0,1 个数相同的串} 是非正则的. 从而 L' 的补语言 L 是非正则的.
⑹ 泵引理（形式语言与自动机理论）正规语言
形式语言 形式语言是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。 语言的形式定义 字母表∑为任意有限集合,ε表示空串,记∑0为{ε},全体长度为n的字串为∑n,∑*为∑0∪∑1∪…∪∑n...