练习题 -- 程序语言基础 >> 文法与自动机
共 6 题
第 1/6 题
★★
以下文法类型中，与下推自动机等价的是：
正确答案: C
Chomsky文法分类体系：0型（短语结构）↔ 图灵机，1型（上下文有关）↔ 线性有界自动机，2型（上下文无关）↔ 下推自动机，3型（正则）↔ 有限自动机。程序语言的语法通常用2型文法（BNF）描述。
第 2/6 题
★
程序设计语言中的语法一般用BNF范式描述，BNF描述的是：
正确答案: C
BNF（Backus-Naur Form，巴科斯范式）是描述上下文无关文法（2型文法）的标准形式化记法。程序语言的语法规则（如if语句、循环语句的定义）用BNF可以精确描述，且恰好落在上下文无关文法的范畴内。
第 3/6 题
★
以下对高级语言的描述，正确的是：
正确答案: D
高级语言与机器无关，具有良好的可移植性。编译型语言（如C/C++）将源代码一次性编译为机器码，执行速度快。解释型语言（如Python/JavaScript）边解释边执行，开发效率高但执行速度相对较慢。
第 4/6 题
★
一个DFA有3个状态，输入字母表有2个符号。其状态转移表共有几项？
正确答案: B
DFA的状态转移表行对应状态、列对应输入符号。转移表项数 = 状态数 × 输入字母表符号数 = 3 × 2 = 6。每个表项给出当前状态读入当前输入后的下一个状态。
第 5/6 题
★★
确定有限自动机(DFA)和非确定有限自动机(NFA)的关系是：
正确答案: C
DFA（确定有限自动机）和NFA（非确定有限自动机）识别相同的语言类——正则语言（正则文法/3型文法描述的语言）。任何NFA都可以通过子集构造法转换为等价的DFA，反之DFA也是NFA的特例。
第 6/6 题
★★
正则表达式(ab)*描述的字符串集合不包括：
正确答案: D
正则表达式(ab)*表示空串或任意多个ab连接而成的字符串：ε、ab、abab、ababab...（以ab为基本重复单元）。aba不在该集合中，因为aba不能由若干个ab连接而成。