编译原理形式语言文法题目

第二章 形式语言与文法练习题

姓名： 学号： 1101070211 班级：2班 一、单选题

1.给定文法：A→bA|cc,下面的符号串为该文法句子的是（ ）。 ① cc ② bcbcc ③ bccbcc ④ bbbcc A. ①④ B. ①②③ C. ①③ D. ②③④ 2.文法G[Z]和语言L（G[Z ]）存在如下关系（ ）。

A.一一对应：一个文法对应唯一的语言；并且反过来，一个语言对应唯一的文法。 B.一个语言对应唯一的文法，反之则不然。 C.一个文法对应唯一的语言，反之则不然。

D.若G为非二义性文法，则C是正确的；若G为二义性文法，则一个文法不对应唯一的语言。

3. 有文法G[E]：E→－EE， E→－E，E →a|b|c 则文法的句子－－a－bc的所有可能的语法树有（ ）棵。

A. 1 B. 2 C. 4 D. 3 4.有文法G[S]，如果S

x，( x∈VT )，则x是（ ）。

A. 句型 B. 句

第3章文法和语言 第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc

写出L(G[S])的全部元素。 答案：

L(G[S])={abc} 第2题

文法G[N]为： N→D|ND

D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD....=>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]:

S->S+D|S-D|D

D->0|1|2|3|4|5|6|7|8|9 第4题

已知文法G[Z]： Z→aZb|ab

写出L(G[Z])的全部元素。 答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb L(G[Z])={anbn|n>=1} 第5题

写一文法，使其语言是偶正整数的集合。要求： (1)允许0打头； (2)不允许0打头。 答案：

(1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D

N→D|1|3|5|7

第3章文法和语言

第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为：

S→Ac|aB

A→ab

B→bc

写出L(G[S])的全部元素。

答案：

L(G[S])={abc}

第2题

文法G[N]为：

N→D|ND

D→0|1|2|3|4|5|6|7|8|9

G[N]的语言是什么？

答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}

N=>ND=>NDD....=>NDDDD...D=>D......D

或者：允许0开头的非负整数？

第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：

G[S]:

S->S+D|S-D|D

D->0|1|2|3|4|5|6|7|8|9

第4题

已知文法G[Z]：

Z→aZb|ab

写出L(G[Z])的全部元素。

答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb

L(G[Z])={anbn|n>=1}

第5题

写一文法，使其语言是偶正整数的集合。要求：

(1)允许0打头；

(2)不允许0打头。

答案：

(1)允许0开头的偶正整数集合的文法

E→NT|D

T→NT|D

N→D|1|3|5|7|9

D→0

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

关于

《结构化程序设计思想在形式语言与自动机理论中的体现》 一文中性质语言与自动机相关理论知识的分析与感悟

————戚洪源

摘 要：本文为本科阶段学习形式语言与自动机课程过程中阅读专业文献后，对于该文献中所涉及的形式语言与自动机的专业知识进行解读和分析，以及一些个人在学习形式语言与自动机课程后的感悟。

关键词：形式语言与自动机 结构化程序设计 计算机理论 正 文：

一、关于文献中形式语言与自动机相关知识的解读 （一）文章第二部分涉及到的关于正则文法的相关知识

文章的第二部分：构造文法时结构化思想的体现。在这一部分中，作者举了一个经典的正则文法的例子：

S?R?R?R0R?NBPB?N.DP?0.DN?AMA?123...89M??0M1M2M3M...8M9MD?MA

首先我们运用学过的知识将这个文法转化为一个等价的正则文法：

定义2.5 若对于文法G=(V,T,P,S),P中每个产生式都有如下形式：

A?a或A?aB,a?T????,A,B?V

则称G为正则文法。

在这个文法中，除了第三行、第四行、第五行、第八行，每一个语句都满足正则文法语句的要求。而对于第五行，可以转化为：

N?0M1M2M...8M9M

浅谈当代艺术中的材料形式语言

在当代艺术这个缤彩纷呈的艺术时代，不同的艺术风格、流派都不约而同的采用材料形式这种新形式来表达自己所见所闻，所感所想。所幸的是这种新的形式语言在艺术中产生了积极的推进作用，并用它自身的优势在当代艺术中占有了一席之地，随着艺术家对它探索研究的深入，很有越演越烈的趋势。本文旨在说明材料形式艺术的本质，内涵，对艺术、对艺术家、对人类生活所起到的作用，及与其他艺术形式的关系。让材料形式艺术能被更多人了解，接受，运用或欣赏，从而不论是艺术家还是观赏者都能从材料形式艺术中体会到愉悦与欣喜。

一、材料形式在当代艺术中的产生与发展

在当代艺术与设计中，材料形式被艺术家当作最为直接的表现思想与观念的媒介广泛运用，材料形式具有了独立的审美价值，材料形式在当代艺术中扮演越来越重要的角色。所谓材料形式语言，是指非绘画性物质材料形式（如杂草，木块，报纸，纤维质地的物品等等）直接拼贴应用到创作中，使它成为阐述作品的一种形式语言。材料形式语言是当代艺术表现形式新的扩展，因为它的出现，打破了传统绘画和非绘画的界限，同样传统的绘画和雕塑的界限也打破了，艺术贴近了人类的生活。在传统形式语言的基础上，加入了肌理语言和材料形式语言，表现形式更加丰富有力

形式语言与自动机课后作业答案

第二章

4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB

B→y B→yC C→y C→yD D→y

6．构造上下文无关文法能够产生

L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa

7．找出由下列各组生成式产生的语言（起始符为S） (1) S→SaS S→b (2) S→aSb S→c

(3) S→a S→aE E→aS

答：（1）b(ab)n /n≥0}或者L={(ba)nb /n≥0}

(2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0}

第三章

1． 下列集合是否为

形式语言与自动机理论试题

一、按要求完成下列填空

1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串

(2)所有既没有一对连续的0，也没有一对连续的1的串 1. 构造识别下列语言的DFA (2x6) (1) {x|x?{0，1}+且x以0开头以1结尾}

(2) {x|x?{0，1}

+

且x的第十个字符为1}

二、判断（正确的写T，错误的写F） 5x2'

1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则

(R1?R2)R3?R1R3?R2R3

A 2.对于任一非空集合A，Φ?2

3.文法G：S A|AS A a|b|c|d|e|f|g 是RG 4.3型语言

2型语言

1型语言

0型语言

?? 5.s（rs+s）*r=rr*s（rr*s）*

三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。

S?aBC|aSBC aB?ab

bB→bb

?

CB→BC bC→bc c

形式语言与自动机课后作业答案

第二章

4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB

B→y B→yC C→y C→yD D→y

6．构造上下文无关文法能够产生

L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa

7．找出由下列各组生成式产生的语言（起始符为S） (1) S→SaS S→b (2) S→aSb S→c

(3) S→a S→aE E→aS

答：（1）b(ab)n /n≥0}或者L={(ba)nb /n≥0}

(2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0}

第三章

1． 下列集合是否为

实验七：LL(1)文法的判断

一：要求

输入：任意的上下文无关文法。 输出：判断是否为LL（1）文法

二：实验目的

1． 掌握LL(1)的判断，掌握求first和follow集合的算法 2． 熟悉运用C/C++语言对求first和follow集合进行实现

三：实验原理

设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1；

（1） 若xi∈VT，则xi∈FIRST（α）； （2） 若xi∈VN； ① 若ε FIRST（xi），则FIRST（xi）∈FIRST（α）； ② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； （3） i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε FIRST（xi）或i>n为止。

当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。

设文法G[S]＝（VN，VT，P，S），则

FOLLOW（A）＝{a | S … Aa …