自动机理论|集1

在GATE CS考试中提出了以下问题。 1.设S和T是＝{a，b}上的语言，分别由正则表达式（a+b*）*和（a+b）*表示。以下哪项是正确的？（门CS 2000） （a） ScT（S是T的子集） （b） TcS（T是S的子集） （c） S=T （d） SnT=Ø

答复: （c） 。

2.让L表示语法S–OSO/00生成的语言。以下哪项是正确的？（门CS 2000） （a） L=O （b） 我是普通人，但不是O （c） L是上下文无关的，但不是常规的 （d） L不是上下文无关的

答复: （b） 说明： 请注意，语法本身不是规则的，但语言L是规则的，因为L可以用规则语法表示，例如S->S00/00。 参考资料： http://en.wikipedia.org/wiki/Regular_grammar

3、考虑以下两个陈述： S1:{0^2n | n>=l}是一种常见的语言 S2:{0^M0^N0^（m+n）LM>=1和n>=2}是一种常见的语言 以下哪项陈述是正确的？（CS门2001） a） 只有S1是正确的 b） 只有S2是正确的 c） S1和S2都是正确的 d） S1和S2都不正确

答复: （c） 说明： S1可以写成（00）^n，其中n>=1。S2可以写成（00）^（m+n），其中m>=2和n>=1。S2可以进一步减少到（00）^x，其中x>=3。 我们可以很容易地为S1和S2编写规则语法。 G1->G100/00（适用于S1） G2->G200/000000（用于S2）

4.下列哪项陈述是正确的？（CS门2001） （a） 如果一种语言是上下文无关的，那么它总是可以被确定性下推自动机接受 （b） 两种上下文无关语言的结合是上下文无关的 （c） 两种上下文无关语言的交集是上下文无关的 （d） 上下文无关语言的补语是上下文无关的

答复: （b） 说明： 上下文无关语言在以下操作下关闭。也就是说，如果L和P是上下文无关语言，D是常规语言，那么以下语言也是上下文无关语言： •克莱恩星 •同态Ø下L的图像Ø（L） •L和P的串联 •L和P的结合 •L与正规语言D（L n D）的交叉点。 上下文无关语言在补语、交集或差分下是不封闭的。 为什么a）不是真的？ 确定性下推自动机识别的语言是确定性上下文无关语言。并非所有上下文无关的语言都是确定性的。这与确定性有限自动机的情况不同，确定性有限自动机也是非确定性有限自动机的子集，但可以识别同一类语言（如子集构造所示）。 参考资料： http://en.wikipedia.org/wiki/Context-free_language http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton

5.给定具有N个状态的任意非确定性有限自动机（NFA），等价最小化DFA中的最大状态数至少为。（CS门2001） （a） N^2 （b） 2^N （c） 2N （d） N！

答复: （b） 参考资料： http://en.wikipedia.org/wiki/Powerset_construction