11年有限自动机理论试题

有限自动机理论试题 本资源为电子科技大学2011年有限自动机理论期末考试试题，涵盖自动机理论的多个方面，包括有限自动机、图灵机、PDAM等。试题共七题，分别考察了有限自动机的文法构造、图灵机的设计、PDAM的设计、自动机的识别语言等。 一、字母表为{a，b，c}，构造下列语言的文法： 本题考察了有限自动机的文法构造。给定字母表{a，b，c}，需要构造两个语言的文法：{x|x=xT, x∈Σ+}和{w|w∈Σ+，且w中a，b的个数一样多}。这两个语言的文法构造需要使用有限自动机的基本概念，如语言、文法、自动机等。 二、构造 TM，计算 n+m+k： 本题考察了图灵机的设计。需要构造一个图灵机来计算n+m+k，考察了图灵机的基本概念，如图灵机的构成、图灵机的计算模型等。 三、构造识别下列语言的 NFA： 本题考察了有限自动机的识别语言。需要构造一个NFA来识别语言{w|w∈{0,1}+;且如果w以10结尾，则w的长度为偶数；如果w以1结尾，则w的长度为奇数}。这道题需要使用有限自动机的基本概念，如NFA、DFA、语言识别等。 四、构造识别下列语言的 DFA： 本题考察了有限自动机的识别语言。需要构造一个DFA来识别语言{x|x∈{0,1}+；且x中最多只能含一个00子串}。这道题需要使用有限自动机的基本概念，如DFA、语言识别等。 五、构造 PDAM 接受语言 L={anb2man|n,m>=1}： 本题考察了PDAM的设计。需要构造一个PDAM来接受语言L={anb2man|n,m>=1}，考察了PDAM的基本概念，如PDAM的构成、PDAM的计算模型等。 六、构造 3 道图灵机进行二进制数的加法运算： 本题考察了图灵机的设计。需要构造三个图灵机来进行二进制数的加法运算，考察了图灵机的基本概念，如图灵机的构成、图灵机的计算模型等。 七、利用图灵机的子程序技术，构造 Turing M，求非负整数的除法： 本题考察了图灵机的设计和子程序技术。需要构造一个图灵机来求非负整数的除法，考察了图灵机的基本概念，如图灵机的构成、图灵机的计算模型、子程序技术等。