如何定义上下文无关文法？

一、如何定义上下文无关文法？

在两种符号置换的意义下(终结符和非终结符分别替换), 许多文法之间有着相似性。把一组彼此相似的文法抽象成一个更高级的形式体系，就叫作文法形式。迄今，文法形式的研究主要集中在上下文无关文法上。

文法形式的具体定义是：给定无限的终结符表Σ∞和无限的非终结符表V∞。任取Σ∞和V∞的非空子集Σ和V,按构造普通文法的方法定义一个四元组G=(Σ，V，S，P)。在G确定以后，任取映射函数ψ，把Σ中每一元素a映为Σ∞中一有限子集ψ(a)，把V中每一元素A映为V∞中一个有限子集ψ(A),且当A厵B时有ψ(A)∩ψ(B)=φ。ψ就是所需的置换。通过它得到一个具体文法ψ(G)=【ψ(Σ)，ψ(V),ψ(S),ψ(P)】,其中ψ(P)是把P中所有产生式中的符号作ψ置换后得到的一组新产生式，ψ(Σ),ψ(V)和ψ(S)分别是ψ(P)中出现的终结符集，非终结符集和出发符号。 这样的G称为文法形式，ψ称为G的一个解释，ψ(G)是G的一个解释文法，被认为是相似于G。令ψ遍历各种可能的解释,得到的ψ(G)集合称为G的文法性语言族，由此生成的语言集合(ψ(G))称为G的文法性语言族。例如，文法形式{S→aS，S→a}的文法性语言族是正则语言集;{S→SS，S→a}的文法性语言族是上下文无关语言集。

若文法形式G作为普通文法时生成的语言(G)是无限集，则称G为非平凡的。此时文法性语言族(G)是一个满主半AFL，反之不然。如满主半AFL({ab│n≥1})，不是一个文法性语言族。

以G1·G2表文法性语言族G1和G2的乘积,1∩2表两者之并,它们仍是文法性语言族。当吇G1G2时，必有G吇G1或G吇G2成立，则称G是素的。正则语言集和线性语言集都是素文法性语言族。任一文法性语言族G必可唯一地分解为它的素因子乘积和：G=(11…1n1)∪…∪(m1…mnm)。其中每个Gij都是素因子。这个分解在乘积运算∪可交换的意义下是唯一的。 从文法生成语言，可有多种推导公式。例如文法{S→AB，A→a,B→b}可有两种推导：S崊AB崊aB崊ab及S崊AB崊Ab崊ab。若每次都取最左边的非终结符进行推导，如上例中的前一种方式那样，则称为左推导。如果有两种不同的左推导推出同一结果，则称此文法是二义性的，反之是无二义文法。对有些二义性文法，可找到一个等价的无二义文法，生成同一个语言。不具有无二义文法的语言称为本质二义性语言。例如，{S→A,S→a,A→a}是二义性文法。

是本质二义性语言。

二、什么是概率上下文无关文法？

上下文无关文法能描述一个能被下推自动机识别的语言，即上下文无关语言；图灵机可以识别递归可枚举语言。X图灵等价是指X能做图灵机能做的所有事情， 图灵机能做X能做的所有事情。X图灵完备是指X能做图灵机能做的所有事情。通常说X编程语言是上下文无关语言是指能通过X编程语言的语法分析的语言是上下文无关语言，也就是说识别通过X编程语言的语法分析的语言的文法是上下文无关文法。而实际上，能通过X编程语言的编译的语言完全可能是递归可枚举语言。举个例子，通过C++的语法分析的语言是上下文无关语言（这里可能不是很严格，有可能通过语法分析的时候就已经不是上下文无关语言了），也就是说下面代码可能就能通过C++的语法分析，然而它并不能通过编译。

而由于C++强大的模板功能，所以实际上能通过C++的编译的语言实际上应该是递归可枚举语言。所以编译C++的自动机是图灵等价的（有趣的结论：我们可以写一个C++程序，使得编译器的编译过程陷入死循环；当然，这里的图灵等价不是严格的，毕竟我们的机器的存储空间不是无限的）。对于编译出来的文件，因为都是执行在图灵等价的计算机上（这里的图灵等价也不是严格的，理由跟之前一样），所以编译出来的文件最极限的就是能做所有图灵机能做的事情，因此，如果编译出来的文件是图灵等价的，那么他就已经到达极限了。不过是否有一个自动机能做图灵机做不了的事情现在还没有定论，所以如果存在这样的机器（比如假想的

Oracle machine

），就可以有不是图灵等价并且是图灵完备的编程语言了。因此：1.那如果文法就是图灵等价的，写出的程序会不一样么？不会。2.还是说二者本来就没关系，语言用哪类文法不过是设计者随性而为。没有关系。不是随性的吧。3.或者说因为图灵机定义了程序能力的上限，当然。不过可能有比图灵机更厉害的自动机哦，如果在上面跑程序就突破图灵机的上限了。4.所以反过来，语言文法越简单越好，比如3型文法更好？都说了不是随性的啦。

三、上下无关文法的定义？

程序设计语言的语法基本上都是上下文无关文法，应用十分广泛。

在计算机科学中，若一个形式文法G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。

上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。

四、python怎么删除无关列？

1、使用del函数删除指定列

python 中针对DataFrame格式的数据,删除列最简单的方法是使用del 函数,简单粗暴效果好,如import pandas as pd

df = pd.DataFrame(columns = list('AB'),data = [[1,2,3],[4,5,6]])

print(df)

结果如下:

A B C

0 1 2 3

1 4 5 6

#删除B列

del df['B']

print(df)

结果如下:

A C

0 1 3

1 4` 6

DataFrame是一种表格型数据结构，它含有一组有序的列，每列可以是不同的值。DataFrame既有行索引，也有列索引，它可以看作是由Series组成的字典，不过这些Series公用一个索引。

2、使用DataFrame.drop函数删除指定列

用法：DataFrame.drop(labels=None,axis=0, index=None, columns=None, inplace=False)

参数说明：

labels 就是要删除的行列的名字，用列表给定

axis 默认为0，指删除行，因此删除columns时要指定axis=1；

index 直接指定要删除的行

columns 直接指定要删除的列

inplace=False，默认该删除操作不改变原数据，而是返回一个执行删除操作后的新dataframe；

inplace=True，则会直接在原数据上进行删除操作，删除后无法返回。

五、python简单编程题与7无关的数？

#include<stdio.h> int main() { int n,i,sum=0; while(1) //这里最好加上对于n的判断 { printf("plaese input: "); scanf("%d",&n)

; if(n>0&&n<100) break; else printf("error input!\n"); } for(i=1;i<=n;i++) { if(i%7==0)continue; //这里用i，不是n！！！！！！！

if((i%10==7)||(n/10==7))continue;//这里用i，不是n！！！！！！！

sum+=i*i; } printf("%d\n",sum); return 0; }